complexité

Répondre

Messages : 47

Enregistré le : 18 août 2017 22:22

Classe : MP

complexité

Message par taupin98 » 06 avr. 2018 18:13

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.

Messages : 2042

Enregistré le : 27 oct. 2017 10:55

Classe : Bac a fleurs

Re: complexité exponentielle et quasi lineaire

Message par Hibiscus » 06 avr. 2018 18:24

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)
Lycée Masséna (Pcsi-PC*) -- École polytechnique (X2015) -- Ex-PhD Student (Japon, Astrophysique)

Messages : 11378

Enregistré le : 30 juil. 2008 16:59

Classe : Dr.-Ing

Re: complexité

Message par fakbill » 11 avr. 2018 17:56

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é.

Répondre