complexité

Modérateur : Michel Quercia

Répondre
taupin98
Messages : 47
Enregistré le : ven. août 18, 2017 10:22 pm
Classe : MP

complexité

Message par taupin98 » ven. avr. 06, 2018 6:13 pm

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.

Avatar du membre
Hibiscus
Messages : 1225
Enregistré le : ven. oct. 27, 2017 10:55 am
Classe : Bac a fleurs

Re: complexité exponentielle et quasi lineaire

Message par Hibiscus » ven. avr. 06, 2018 6:24 pm

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)
Université de Tokyo/Tohoku - Astrophysique

Avatar du membre
fakbill
Messages : 11134
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: complexité

Message par fakbill » mer. avr. 11, 2018 5:56 pm

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

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité