Qu'est-ce que Complexité temporelle (notation grand O) ?
Description de la façon dont le travail (complexité temporelle) ou la mémoire (complexité spatiale) nécessaires à un algorithme croissent avec le nombre de données n. Elle s'écrit en notation grand O, par exemple O(n), O(n log n) ou O(n²), en omettant les facteurs constants et les termes de degré inférieur.
Nom japonais: 計算量
« Complexité temporelle (notation grand O) » apparaît dans 7 questions d'entraînement réparties sur 1 thèmes, dont Structures de données et algorithmes.
Domaine: Structures de données et algorithmes
Lire la notation grand O
O(f(n)) signifie que, pour n suffisamment grand, le travail reste inférieur à un multiple constant de f(n). Un algorithme qui effectue 3n² + 5n + 2 comparaisons s'écrit O(n²), car le terme en n² domine quand n croît. Les classes courantes sont, par ordre croissant, O(1) (constante), O(log n) (recherche dichotomique), O(n) (recherche linéaire), O(n log n) (tri fusion, tri par tas), O(n²) (tri à bulles, tri par sélection) et O(2ⁿ) (recherche exhaustive naïve). Pour n = 1000, log₂ n vaut environ 10, n log₂ n environ 10 000, et n² vaut 1 million : pour de grandes quantités de données, la différence de complexité est décisive.
Meilleur cas, cas moyen et pire cas
Un même algorithme peut faire plus ou moins de travail selon l'entrée. Le tri par insertion effectue n−1 comparaisons, O(n), sur des données triées, mais n(n−1)/2, O(n²), sur des données en ordre inverse. Le tri rapide est en O(n log n) en moyenne mais en O(n²) dans le pire cas, selon le choix du pivot et les données. Les systèmes qui ont besoin d'une borne sur le temps de réponse s'intéressent au pire cas, tandis que les estimations du débit global utilisent le cas moyen. Quand une étape coûteuse occasionnelle se ramène en moyenne à une constante sur de nombreuses opérations, comme l'ajout dans un tableau dynamique, on parle de coût O(1) amorti.
La vitesse réelle ne dépend pas que de la complexité
Comme la notation grand O ignore les facteurs constants, deux algorithmes en O(n) peuvent avoir des vitesses réelles très différentes. Sur les ordinateurs modernes, la mémoire principale est près de 100 fois plus lente que le cache L1 : lire un tableau dans l'ordre est donc bien plus rapide que parcourir une liste chaînée. Pour un petit n, un algorithme simple de complexité moins bonne peut aussi être plus rapide, ce qui explique que les implémentations pratiques des tris utilisent le tri par insertion pour les courtes plages. Pour améliorer les performances, on vérifie d'abord qu'aucun algorithme de complexité inutilement élevée n'est utilisé, puis on mesure et on affine les détails comme les schémas d'accès à la mémoire.
Questions fréquentes
Quelle est la base du logarithme dans O(log n) ?
Changer de base ne modifie la valeur que d'un facteur constant (log₂ n = log₁₀ n ÷ log₁₀ 2) : la notation grand O l'omet donc généralement. Pour les algorithmes qui divisent les données par deux à chaque étape, comme la recherche dichotomique, le nombre réel d'étapes est proche de log₂ n.
Quelle est la différence entre complexité temporelle et complexité spatiale ?
La complexité temporelle décrit la croissance du travail (du temps d'exécution), et la complexité spatiale celle de la mémoire nécessaire. On compare les deux ensemble : le tri fusion est en O(n log n) en temps avec un espace de travail en O(n), alors que le tri par tas est en O(n log n) en temps avec un espace en O(1).