complexité

Messages : 0

Inscription : 18 août 2017 22:22

Profil de l'utilisateur : Élève de lycée

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 : 294

Inscription : 27 oct. 2017 10:55

Profil de l'utilisateur : Professionnel

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)
Masséna (PC*) -- X15 -- Spatial.

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

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