AnalyseNotion · Glossaire
complexité temporelle
La complexité temporelle décrit comment le nombre d'opérations élémentaires exécutées par un algorithme croît avec la taille de l'entrée, pour un modèle de coût et un cas d'analyse donnés. Une borne O(n²) signifie qu'asymptotiquement ce nombre est majoré par une constante fois n², sans prédire exactement le temps réel. Elle sert à comparer la croissance des besoins en calcul de plusieurs algorithmes lorsque la taille des données augmente.
Sommaire
Ce que vous allez apprendre
- Relier la taille d'une entrée au nombre d'opérations d'un algorithme.
- Interpréter grand O comme une borne asymptotique sous un modèle de coût annoncé.
- Refaire une recherche dichotomique sur 16 valeurs et contrôler ses trois comparaisons.
- Distinguer complexité temporelle, durée mesurée et complexité spatiale.
En clair
Imaginez que vous cherchiez 42 dans une liste triée de 16 nombres. Vous pouvez lire les nombres un à un, ou regarder au milieu et éliminer à chaque fois la moitié devenue inutile. Dans notre liste, cette seconde méthode trouve 42 après trois comparaisons.
La complexité temporelle décrit la manière dont ce travail augmente quand la liste grandit. Elle ne donne pas un temps en secondes : elle met en évidence le rythme de croissance du nombre d'opérations, afin de comparer des méthodes au-delà d'une machine particulière.
Définition
Pour une taille d'entrée notée n, la complexité temporelle étudie une fonction T(n) qui compte les opérations élémentaires exécutées par un algorithme selon un modèle de coût fixé. L'analyse asymptotique s'intéresse à la croissance de T(n) lorsque n devient grand. Elle néglige alors les facteurs constants et les termes de moindre ordre, sans prétendre qu'ils sont négligeables pour toute entrée réelle.
Dire que T est en grand O d'une fonction g signifie qu'il existe une constante positive c et un seuil n0 tels que, pour toute taille n au moins égale à n0, T(n) soit au plus égale à c fois g(n).
Le cas étudié doit être précisé : meilleur cas, pire cas, ou coût moyen sous une distribution d'entrées donnée. Grand O exprime une borne supérieure ; la notation thêta, Θ, exprime un ordre de croissance à la fois supérieur et inférieur. Ainsi, écrire O(n²) n'affirme pas à lui seul que le comportement est exactement quadratique.
Un exemple, pas à pas
On cherche le nombre 42 par recherche dichotomique dans la liste triée suivante : 3, 7, 11, 14, 18, 22, 27, 31, 36, 42, 47, 53, 58, 64, 71, 79. La taille n de l'entrée vaut 16, et une opération comptée est la comparaison entre 42 et la valeur centrale de l'intervalle encore possible.
1. Comparez 42 à 31, valeur de rang 8. Comme 42 est plus grand, les rangs 1 à 8 sont éliminés.
2. Dans les rangs 9 à 16, comparez 42 à 53, de rang 12. Comme 42 est plus petit, les rangs 12 à 16 sont éliminés.
3. Dans les rangs 9 à 11, la valeur centrale est 42, de rang 10. La troisième comparaison conclut la recherche.
Le résultat se contrôle en relisant les trois intervalles : chacun contient encore le rang 10, et leur taille passe de 16 à 8, puis 3, avant l'égalité. Une lecture séquentielle aurait comparé dix valeurs avant d'atteindre 42. Le chemin des comparaisons rend visible cette réduction successive.
En pratique
Pour chercher souvent dans des données déjà triées, on compare la recherche dichotomique à une lecture séquentielle. Si l'accès direct au milieu est possible, la première divise par deux, à un arrondi près, la taille de l'intervalle restant après chaque comparaison infructueuse ; sinon, le parcours simple peut rester préférable.
Pour choisir entre deux algorithmes qui donnent le même résultat, on exprime leur coût avec la même taille d'entrée et le même modèle d'opération. Une croissance en O(n log n) devient généralement plus favorable qu'une croissance en O(n²) lorsque n augmente, mais les constantes comptent encore pour les petites entrées.
Pour prévoir si un traitement passera à l'échelle, on observe comment le coût évolue quand n double. Un coût linéaire est approximativement multiplié par 2, tandis qu'un coût quadratique l'est par 4 ; ce contraste aide à décider s'il faut changer de méthode avant d'augmenter le volume.
À ne pas confondre
Complexité temporelle et complexité spatiale. La première compte le travail effectué ; la seconde étudie la mémoire mobilisée en fonction de la taille de l'entrée. Deux algorithmes aussi rapides asymptotiquement peuvent donc se distinguer par leur consommation de mémoire.
Complexité et durée mesurée. Une mesure en millisecondes dépend de la machine, du langage, des données et de l'implémentation. Une complexité en O(n) décrit une croissance asymptotique : deux programmes tous deux linéaires peuvent avoir des durées différentes sur la même entrée.
Grand O et thêta. Grand O donne une borne supérieure asymptotique, tandis que Θ décrit un ordre de croissance serré. Par exemple, une fonction T(n) = n est en O(n²), mais elle n'est pas en Θ(n²).
Limites et pièges
Petites entrées. Un algorithme de meilleur ordre asymptotique peut être plus lent tant que n reste sous un certain seuil, à cause de constantes ou d'un coût initial élevés. Il faut alors mesurer les implémentations sur la plage de tailles réellement utilisée.
Taille identique, contenus différents. Pour n = 16, la recherche dichotomique de l'exemple trouve 42 en trois comparaisons, mais une autre valeur peut demander un autre nombre de comparaisons. Il faut annoncer si l'on étudie le meilleur cas, le pire cas ou une moyenne associée à une distribution précise.
Opération mal choisie. Compter chaque instruction comme si elle avait toujours le même coût peut masquer des accès mémoire, des entiers très grands ou des communications. Le modèle de coût doit correspondre aux opérations dominantes du problème étudié.
Plusieurs tailles d'entrée. Réduire trop tôt le coût à une seule variable peut cacher une dépendance. Pour traiter une grille de n lignes et m colonnes, une écriture comme O(nm) conserve l'information que ne donne pas O(n²) lorsque n et m peuvent différer.
Pour aller plus loin
Grand O précise le langage des bornes asymptotiques utilisé pour classer les rythmes de croissance.
algorithme replace l'analyse du coût dans la description d'une suite finie d'instructions exécutables.
complexité spatiale complète l'étude du temps par celle de la mémoire nécessaire quand l'entrée grandit.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres