bonjour tout le monde, svp est ce que vous pouvez m'expliquer chacune des complexités suivantes
logarithmique
polynomiale
quasi linéaire
exponentielle
et merci.
complexité
Re: complexité exponentielle et quasi lineaire
On va imaginer que tu parles de la complexité en temps.
C'est donc, concrètement le nombre d'actions nécessaires, souvent dans le pire cas, (ou aussi en moyenne) pour arriver au résultat attendu par ton algorithme, en fonction de la taille de l'entrée.
Complexité pseudo linéaire : O(n log n), par exemple le tri fusion d'un tableau de taille n
Exponentielle : 2^O(n), un algorithme en force brute, comme le voyageur de commerce.
Puisque tu as changé ton message, j'ajoute
Logarithmique : O(log n), par exemple la recherche dichotomique
Et polynomiale, 2^O(log n) = polynôme(n)
C'est donc, concrètement le nombre d'actions nécessaires, souvent dans le pire cas, (ou aussi en moyenne) pour arriver au résultat attendu par ton algorithme, en fonction de la taille de l'entrée.
Complexité pseudo linéaire : O(n log n), par exemple le tri fusion d'un tableau de taille n
Exponentielle : 2^O(n), un algorithme en force brute, comme le voyageur de commerce.
Puisque tu as changé ton message, j'ajoute
Logarithmique : O(log n), par exemple la recherche dichotomique
Et polynomiale, 2^O(log n) = polynôme(n)
Masséna (PC*) -- X15 -- Spatial.
Re: complexité
et on suppose que chaque "action" élémentaire prend le meme temps.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.