Sur cette page
Un exemple concret
Chercher un élément dans une liste non triée en la parcourant : complexité linéaire. Dans une liste triée, la recherche dichotomique a une complexité logarithmique, bien plus rapide.
Le piège à éviter
Le tri par sélection et le tri par insertion ont une complexité quadratique dans le pire des cas : si la liste est 10 fois plus longue, le temps peut être multiplié par 100.
Pour aller plus loin
Pour comparer des algorithmes, on ne mesure pas le temps en secondes, car il dépend de la machine, du langage et de la charge du processeur. On compte plutôt le nombre d'opérations élémentaires en fonction de la taille n des données. On note souvent O(n), « grand O de n », pour indiquer un ordre de grandeur : les constantes sont ignorées. Cette notation a été popularisée en mathématiques par Edmund Landau. On distingue aussi le meilleur cas, le cas moyen et le pire cas, ce dernier étant le plus souvent étudié car il fournit une garantie.
Voyons l'écart concret entre les classes. Pour chercher une valeur dans une liste d'un million d'éléments, une recherche séquentielle demande au plus 1 000 000 de comparaisons, contre environ 20 pour une recherche dichotomique dans une liste triée, car 2²⁰ = 1 048 576. Pour trier ce million d'éléments, un tri quadratique exige de l'ordre de 10¹² opérations, soit 1 000 secondes à raison de 10⁹ opérations par seconde, environ 17 minutes, alors qu'un tri fusion, en O(n log n), n'en demande que 2 × 10⁷, c'est-à-dire un cinquantième de seconde. Plus n grandit, plus ces différences deviennent décisives.
La notion apparaît en NSI, en Première avec les tris par insertion et par sélection et la recherche dichotomique, puis en Terminale avec la méthode « diviser pour régner ». On y distingue la complexité en temps et la complexité en espace, qui mesure la mémoire utilisée. Les algorithmes exponentiels, de l'ordre de 2ⁿ, deviennent impraticables dès que n dépasse quelques dizaines : c'est pourquoi on cherche des algorithmes plus efficaces ou des solutions approchées. Pour estimer la complexité d'un programme Python, on observe surtout les boucles et leur imbrication.
Ne pas confondre
- Temps d'exécution mesuré : C'est une mesure sur une machine précise. La complexité est une estimation théorique indépendante de la machine, qui décrit la croissance du nombre d'opérations.
- Correction d'un algorithme : Un algorithme correct donne le bon résultat. Un algorithme peut être correct mais très lent, donc de forte complexité.
- Complexité en espace : Elle mesure la quantité de mémoire utilisée, et non le nombre d'opérations. Un algorithme peut être rapide mais gourmand en mémoire.
Dans ta copie
Pour choisir entre deux algorithmes de recherche, j'étudie leur complexité. La recherche séquentielle parcourt la liste élément par élément : dans le pire cas, elle effectue n comparaisons, donc sa complexité est linéaire. La recherche dichotomique coupe l'intervalle en deux à chaque étape, ce qui donne une complexité logarithmique, mais elle exige une liste triée. Pour un million de données, il suffit d'environ vingt comparaisons au lieu d'un million. Je choisirai donc la dichotomie pour des recherches fréquentes dans une liste triée, car le coût du tri préalable est amorti par le grand nombre de recherches.
À retenir
- La complexité compte les opérations en fonction de la taille n des données, pas des secondes.
- On ignore les constantes et on retient le terme dominant : 3n² + 5n est en O(n²).
- Linéaire : O(n) ; quadratique : O(n²) ; logarithmique : O(log n).
- On étudie le plus souvent le pire cas, qui garantit une borne.
Teste-toi
NSI · question corrigée
Quelle est la complexité de la recherche dichotomique dans une liste triée ?
Voir la réponse
Réponse B. On divise l'intervalle de recherche par deux à chaque étape : complexité logarithmique.
NSI · question corrigée
Un algorithme a une complexité quadratique. Si on double la taille des données, le nombre d'opérations est multiplié par environ :
Voir la réponse
Réponse A. Avec une complexité en n², doubler n donne (2n)² = 4n², donc le nombre d'opérations est multiplié par 4.
Questions fréquentes
Pourquoi ignore-t-on les constantes dans la notation O ?
Parce que pour de grandes valeurs de n, c'est le terme dominant qui décide du comportement. Un algorithme en 100n finira toujours par être plus rapide qu'un algorithme en n² si n est assez grand.
Un algorithme peut-il avoir une meilleure complexité dans le meilleur cas ?
Oui. Le tri par insertion est quasi linéaire si la liste est déjà triée, mais quadratique dans le pire cas. C'est pourquoi on précise toujours le cas étudié.
Notions liées
Pour réviser tout le chapitre, va sur la page NSI, ou retrouve toutes les définitions dans le lexique du bac. Dans l'application, les quiz reprennent ces notions sur le programme de ta série.