Analyse de la complexité des algorithmes — Wikipédia

Cet article est en cours de réécriture ou de restructuration importante (26 avril 2025).

Un utilisateur prévoit de modifier cet article pendant plusieurs jours. Vous êtes invité(e) à en discuter en page de discussion et à participer à son amélioration de préférence en concertation pour des modifications de fond.
Bandeau apposé par Tomberanget (d · c) le 26 avril 2025.

L'analyse de la complexité d'un algorithme consiste en l'étude formelle de la quantité de ressources (par exemple de temps ou d'espace) nécessaire à l'exécution de cet algorithme. Celle-ci ne doit pas être confondue avec la théorie de la complexité, qui elle étudie la difficulté intrinsèque des problèmes, et ne se focalise pas sur un algorithme en particulier.

Quand les scientifiques ont voulu énoncer formellement et rigoureusement ce qu'est l'efficacité d'un algorithme ou au contraire sa complexité, ils se sont rendu compte que la comparaison des algorithmes entre eux était nécessaire et que les outils pour le faire à l'époque^[1] étaient primitifs. Dans la préhistoire de l'informatique (les années 1950), la mesure publiée, si elle existait, était souvent dépendante du processeur utilisé, des temps d'accès à la mémoire vive et de masse, du langage de programmation et du compilateur utilisé.

Une approche indépendante des facteurs matériels était donc nécessaire pour évaluer l'efficacité des algorithmes. Donald Knuth fut un des premiers à l'appliquer systématiquement dès les premiers volumes de sa série The Art of Computer Programming. Il complétait cette analyse de considérations propres à la théorie de l'information : celle-ci par exemple, combinée à la formule de Stirling, montre que, dans le pire des cas, il n'est pas possible d'effectuer, sur un ordinateur classique, un tri général (c'est-à-dire uniquement par comparaisons) de N éléments en un temps croissant avec N moins rapidement que N ln N.

L'approche la plus classique est donc de calculer le temps de calcul dans le pire des cas.

Il existe au moins trois alternatives à l'analyse de la complexité dans le pire des cas. La complexité en moyenne des algorithmes, à partir d'une répartition probabiliste des tailles de données, tente d'évaluer le temps moyen que l'on peut attendre de l'évaluation d'un algorithme sur une donnée d'une certaine taille. La complexité amortie des structures de données consiste à déterminer le coût de suites d'opérations. L'analyse lisse d'algorithme, plus récente, se veut plus proche des situations réelles en calculant la complexité dans le pire des cas sur des instances légèrement bruitées.

Parfois, l'analyse de la complexité d'un algorithme est trompeur. En effet, on peut trouver un algorithme disposant d'une meilleure complexité asymptotique mais n'étant pas utilisable en pratique car une constante cachée est si grande que l'algorithme ne sera jamais utilisé pour un jeu de donnée trouvé sur Terre.

Afin d'analyser une complexité d'un algorithme ${\displaystyle A}$ s'exécutant sur un ensemble d'instances ${\displaystyle I}$ on procède en plusieurs étapes :

La première consiste à déterminer une fonction de coût ${\displaystyle c_{A}:I\rightarrow \mathbb {R} ^{+}}$, représentant au choix soit le coût en temps, par exemple nombre d'étapes nécessaires, soit le coût en espace, par exemple le nombre d'octets occupés simultanément, de l'exécution de l'algorithme ${\displaystyle A}$ sur l'entrée ${\displaystyle i\in I}$^[2].

Ensuite, comme l'on veut déterminer le comportement pris par l'algorithme ${\displaystyle A}$ en fonction d'une taille des instances ${\displaystyle i\in I}$, il faut alors déterminer cette taille des instances ${\displaystyle |i|:I\rightarrow \mathbb {N} }$. Cela peut par exemple être le nombre de caractères d'une chaîne de caractère.

Après, l'on doit choisir choisir une mesure de coût ${\displaystyle C:\mathbb {N} \rightarrow \mathbb {R} ^{+}}$, afin d'évaluer le coût de l'algorithme en fonction de la taille des instances et non plus des instances elles même. La mesure la plus utilisée est le coût dans le cas le plus défavorable mais l'on peut aussi choisir le coût dans le cas le plus favorable ou encore le coût moyen^[2].

Enfin, pour comparer le comportement asymptotique de notre mesure de coût et à d'autres mesures, on raisonne alors sur des ordres de grandeurs de croissance^[3]. On peut vouloir montrer une majoration ${\displaystyle {\mathcal {O}}}$, une minoration ${\displaystyle \Omega }$ ou les deux bornes ${\displaystyle \Theta }$.

Analyser la complexité temporelle d'un algorithme, c'est compter le nombre d'opérations élémentaires réalisées par cet algorithme^[2].

Les opérations élémentaires comme les opérations arithmétiques, les opérations booléennes, les affectations, les conditions de branchement n'ont pas toutes le même coût. Il est alors aussi difficile qu'inutile de chercher à compter de manière exhaustive toutes les opérations élémentaires réalisées par un algorithme sur une instance. Afin d'obtenir un ordre de grandeur intéressant selon le contexte, on sélectionnera les opérations que l'on veut compter^[2].

Pour toute la famille des tri par comparaison, c'est uniquement la métrique du nombre de comparaisons que l'on compte. Pour autant, pour des tris externes, la métrique du nombre d'accès tableau est couramment utilisée^[2].

Lorsque l'on calcule le nombre d'opérations élémentaires, le coût, effectuées par une suite d'opérations sur une structure de donnée. Ce coût est donc la somme des coût des opérations individuelles^[3].

Si l'on dispose d'une estimation du coût dans le cas le plus défavorable, des opérations individuelles, on obtient une majoration du coût total en sommant ces majorations^[3].

Or, très souvent, cette majoration est très grossière, car le cas le plus défavorable « ne se répète pas », il y a une « compensation » de coût au cours de la suite d'opérations^[3].

Une analyse plus précise que la majoration grossière est appelée analyse amortie.

La complexité spatiale d'un algorithme représente la quantité de mémoire utilisée par celui-ci, cette quantité est souvent mesurée en nombre d'octet^[2].

Le coût spatial d'une exécution d'un algorithme est la quantité maximale de mémoire utilisée simultanément par cet algorithme au cours de l'exécution^[2].

Déterminer la taille d'une entrée c'est compter le nombre de bits ou d'octet occupés par l'entrée.

Pour un graphe ${\displaystyle G=(S,A)}$, on prendra souvent ${\displaystyle |S|+|A|}$ comme taille du graphe.

Pour n tableau ${\displaystyle T}$ de ${\displaystyle n}$ chacun de taille ${\displaystyle m}$ bits, si la taille réelle est ${\displaystyle n\times m}$. Pourtant, bien souvent on approximera cette taille à ${\displaystyle n}$ car le terme ${\displaystyle m}$ n'apparaît pas dans l'expression du coût. Cela n'est pas possible pour le tri comptage.

Dans l'analyse la complexité du tri comptage, sans hypothèses particulières, on peut facilement calculer par mégarde une complexité erronée. En considérant en entrée le tableau ${\displaystyle T}$ de ${\displaystyle n}$ éléments de ${\displaystyle m}$ bits. Si l'on considère que la taille de l'entrée est ${\displaystyle n}$, on peut alors montrer que l'algorithme est en ${\displaystyle {\mathcal {O}}(n)}$. Or ce raisonnement est erroné, car le nombre réel de bits occupés par l'entrée est ${\displaystyle n\times m}$ la complexité de l'algorithme étant alors ${\displaystyle {\mathcal {O}}(n+2^{m})}$, exponentielle en la taille de l'entrée. Ce résultat est cohérent, car l'hypothèse particulière du tri comptage, nécessaire à l'établissement de la complexité linéaire, est une majoration du nombre ${\displaystyle m}$ de bits, on retombe alors dans le premier cas^[4].

Soit un problème et un algorithme ${\displaystyle A}$ qui le résout. Sur une instance ${\displaystyle x}$ de taille ${\displaystyle n}$, l'algorithme ${\displaystyle A}$ s'exécute sur ${\displaystyle x}$ en un certain nombre d'opérations élémentaires, on appelle ce nombre le cout ${\displaystyle c_{A}(x)}$^[3].

Si le coût d'un algorithme dépend de l'instance d'entrée, elle n'est pas fixée pour une taille donnée. Pour autant, l'objectif est d'évaluer le coût d'un algorithme en fonction de la taille de l'instance. On définit alors trois nuances de fonctions de couts dépendant de ce critère, qui sont des points de repère pour appréhender la complexité réelle^[2].

Le coût dans le cas le plus défavorable d'un algorithme pour les instances de taille ${\displaystyle n}$, noté ${\displaystyle C(n)}$, est le maximum de ses couts sur toutes les instances de taille ${\displaystyle n}$^[3].

Autrement dit, ${\displaystyle C(n)\triangleq {\underset {|x|=n}{max}}(c(x))}$^[5]

Le coût dans le cas le plus favorable d'un algorithme pour les instances de taille ${\displaystyle n}$, noté ${\displaystyle C^{min}(n)}$, est le minimum de ses coûts sur toutes les instances de taille ${\displaystyle n}$^[3].

Autrement dit, ${\displaystyle C^{min}(n)\triangleq {\underset {|x|=n}{min}}(c(x))}$^[5]

Lorsque le cas le plus défavorable est un cas pathologique, on peut vouloir calculer un coût moyen.

Le coût moyen d'un algorithme pour les instances de taille ${\displaystyle n}$, noté ${\displaystyle \gamma _{p}(n)}$, avec ${\displaystyle p(x)}$ est la probabilité d'apparition de l'instance ${\displaystyle x}$ parmi les instances de sa taille, est donc l'espérance des coûts des instances de taille ${\displaystyle n}$^[3].

Autrement dit, ${\displaystyle \gamma _{p}(n)\triangleq {\underset {|x|=n}{\sum }}p(x)c(x)}$^[3].

Le plus souvent, on suppose que toutes les instances d'une taille donnée ont la même probabilité d'apparition.

Le coût moyen uniforme d'un algorithme pour les instances de taille ${\displaystyle n}$, noté ${\displaystyle \gamma (n)}$, en notant ${\displaystyle T(n)}$ le nombre d'instances de taille ${\displaystyle n}$, utilise la distribution de probabilité uniforme ${\displaystyle p(x)=1/T(n)}$^[3].

Autrement dit, ${\displaystyle \gamma (n)\triangleq {\frac {1}{T(n)}}{\underset {|x|=n}{\sum }}c(x)}$^[3].

D'autres fonctions de coût existent comme la complexité générique des algorithmes ou encore l'analyse lisse d'algorithme mais elle sont moins courantes.

Dans l'étude de la complexité d'un algorithme, on s'intéresse à la manière dont la mesure de coût évolue pour des tailles d'instances très grandes. Cette étude du comportement asymptotique de la mesure de coût, est appelée la complexité asymptotique. L'objectif n'étant pas d'obtenir une valeur exacte de cette complexité mais plutôt un ordre de grandeur, on va alors regrouper les différentes fonctions de coûts dans des ensembles exprimant un comportement asymptotique, les notations de Landau^[2].

Les notations de Landau sont un moyen d'exprimer l'ordre de grandeur du nombre d'opérations effectuées ou nécessaires à effectuer par un algorithme pour résoudre un problème. Trois situations sont décrites par ces notations. La plus fréquente, la notation ${\displaystyle {\mathcal {O}}}$ donne une majoration de l'ordre de grandeur. La notation ${\displaystyle \Omega }$ est une minoration de l'ordre de grandeur, et la notation ${\displaystyle \Theta }$ dénote une équivalence sur les ordres de grandeur^[3].

Dans le cadre de la complexité en informatique, on se limite à définir ces notations au voisinage de ${\displaystyle +\infty }$ et pour des fonctions à valeurs positives.

La notation ${\displaystyle {\mathcal {O}}(f)}$, « grand O », est couramment utilisée pour montrer qu'un algorithme de fonction de cout ${\displaystyle c}$ ne s'exécute pas, en ordre de grandeur, en plus d'opérations que ${\displaystyle f}$.

Informellement, on dit que ${\displaystyle c}$ est en ${\displaystyle {\mathcal {O}}(f)}$ lorsque l'on peut majorer ${\displaystyle c}$ par ${\displaystyle f}$ à une constante près^[6].

Par exemple, le tri par insertion est en ${\displaystyle {\mathcal {O}}(n^{2})}$.

Soit ${\displaystyle f:\mathbb {R} \longrightarrow \mathbb {R} ^{+}}$, on désigne par ${\displaystyle {\mathcal {O}}(f)}$ au voisinage de ${\displaystyle +\infty }$ l'ensemble des fonctions de cout positives ${\displaystyle c:\mathbb {R} \longrightarrow \mathbb {R} ^{+}}$ tels qu'il existe ${\displaystyle k,a>0}$ tels que ${\displaystyle c(x)\leqslant kf(x)}$ pour tout ${\displaystyle x>a}$^[3],[2].

Autrement dit, ${\displaystyle {\mathcal {O}}(f)\triangleq \{c\in \mathbb {R} ^{\mathbb {R} ^{+}}|\exists k,a>0,\forall x>a,c(x)\leqslant kf(x)\}}$.

• ${\displaystyle (x\mapsto x)\in {\mathcal {O}}(x^{2})}$^[3]
• ${\displaystyle (x\mapsto {\frac {ln(x)}{x}})\in {\mathcal {O}}(1)}$^[3]
• ${\displaystyle (x\mapsto x+1)\in {\mathcal {O}}(x)}$^[3]

La principale difficulté avec ce concept provient de la convention de notation abusive historique « de Landau » qui veut que l'on écrive ${\displaystyle c={\mathcal {O}}(f)}$ ou encore ${\displaystyle c(x)={\mathcal {O}}(f(x))}$ au lieu de ${\displaystyle c\in {\mathcal {O}}(f)}$^[3].

De la même manière, la convention veut historiquement que l'on écrive ${\displaystyle {\mathcal {O}}(c)={\mathcal {O}}(f)}$ au lieu de ${\displaystyle {\mathcal {O}}(c)\subseteq {\mathcal {O}}(f)}$^[3].

Pour autant, ${\displaystyle c={\mathcal {O}}(f)}$ n'implique pas nécessairement que ${\displaystyle f={\mathcal {O}}(c)}$. De même, ${\displaystyle {\mathcal {O}}(c)={\mathcal {O}}(f)}$ n'implique pas forcément ${\displaystyle {\mathcal {O}}(f)={\mathcal {O}}(c)}$. Dans les deux cas, l'axiome d'égalité est contredit^[3].

La notation ${\displaystyle \Omega (f)}$ caractérise souvent un problème. Elle sert à justifier que tout algorithme résolvant le problème, de fonction de cout ${\displaystyle c}$, ne s'exécute pas, en ordre de grandeur, en plus d'opérations que ${\displaystyle f}$.

Informellement, on dit que ${\displaystyle c}$ est en ${\displaystyle \Omega (f)}$ lorsque l'on peut minorer ${\displaystyle c}$ par ${\displaystyle f}$ à une constante près^[6].

Par exemple, le nombre minimum de comparaisons d'un tri par comparaison est en ${\displaystyle \Omega (n\times log(n))}$^[3].

Soit ${\displaystyle f:\mathbb {R} \longrightarrow \mathbb {R} ^{+}}$, on désigne par ${\displaystyle \Omega (f)}$ au voisinage de ${\displaystyle +\infty }$ l'ensemble des fonctions de cout positives ${\displaystyle c:\mathbb {R} \longrightarrow \mathbb {R} ^{+}}$ tels qu'il existe ${\displaystyle k,a>0}$ tels que ${\displaystyle f(x)\leqslant kc(x)}$ pour tout ${\displaystyle x>a}$^[3],[2].

Autrement dit, ${\displaystyle \Omega (f)\triangleq \{c\in \mathbb {R} ^{\mathbb {R} ^{+}}|\exists k,a>0,\forall x>a,f(x)\leqslant kc(x)\}}$.

Caractérisation : Une fonction ${\displaystyle g}$ appartient à ${\displaystyle \Omega (f)}$ si et seulement si ${\displaystyle f}$ appartient à ${\displaystyle {\mathcal {O}}(g)}$^[6].

De la même manière que pour ${\displaystyle {\mathcal {O}}}$, la convention de notation abusive historique « de Landau » qui veut que l'on écrive ${\displaystyle c=\Omega (f)}$ ou encore ${\displaystyle c(x)=\Omega (f(x))}$ au lieu de ${\displaystyle c\in \Omega (f)}$^[3].

De la même manière, la convention veut historiquement que l'on écrive ${\displaystyle \Omega (c)=\Omega (f)}$ au lieu de ${\displaystyle \Omega (c)\subseteq \Omega (f)}$.

La notation ${\displaystyle \Theta }$ est une relation d'équivalence. On désigne par ${\displaystyle \Theta (f)}$ l'ensemble des fonctions ${\displaystyle c}$ qui « croissent » de façon comparable à ${\displaystyle f}$^[6].

Soit ${\displaystyle f:\mathbb {R} \longrightarrow \mathbb {R} ^{+}}$, on désigne par ${\displaystyle \Theta (f)}$ l'ensemble des fonctions ${\displaystyle c:\mathbb {R} \longrightarrow \mathbb {R} ^{+}}$ pour lesquelles il existe des nombres ${\displaystyle k_{1},k_{2},a>0}$ tels que ${\displaystyle k_{1}\times f(x)\leqslant c(x)\leqslant k_{2}\times f(x)}$^[3],[2].

Autrement dit, ${\displaystyle \Theta (f)\triangleq {\mathcal {O}}(f)\cap \Omega (f)}$.

De la même manière que pour ${\displaystyle {\mathcal {O}}}$ et ${\displaystyle \Omega }$, la notation « de Landau » qui veut que l'on écrive ${\displaystyle c=\Theta (f)}$ ou encore ${\displaystyle c(x)=\Theta (f(x))}$ au lieu de ${\displaystyle c\in \Theta (f)}$^[3].

Pour les algorithmes de type « diviser pour régner », parfois la mesure du coût dépend de celle d'${\displaystyle a}$ sous-problèmes de taille ${\displaystyle n/b}$, il existe un critère général donnant l'ordre de grandeur de telles mesures de coût, il est appelé théorème général ou traditionnellement master theorem^[2].

Ce critère s'applique aux équations de la forme ${\displaystyle C(n)=a\times C({\frac {n}{b}})+f(n)}$^[2]

On appelle exposant critique la valeur ${\displaystyle c_{crit}\triangleq {\frac {log(a)}{log(b)}}=log_{b}(a)}$.

1. Si ${\displaystyle c<c_{crit}}$ et ${\displaystyle f\in {\mathcal {O}}(n^{c})}$ alors ${\displaystyle C(n)\in \Theta (n^{c_{crit}})}$
2. Si ${\displaystyle c=c_{crit}}$ et ${\displaystyle f\in \Theta (n^{c})}$ alors ${\displaystyle C(n)\in \Theta (n^{c}\times log(n))}$
3. Si ${\displaystyle c>c_{crit}}$ et ${\displaystyle f\in \Omega (n^{c})}$ alors ${\displaystyle C(n)\in \Theta (n^{c})}$^[2].

Supposons que le problème posé soit de trouver un nom dans un annuaire téléphonique qui consiste en une liste triée alphabétiquement. On peut s'y prendre de plusieurs façons différentes. En voici deux :

1. Recherche linéaire : parcourir les pages dans l'ordre (alphabétique) jusqu'à trouver le nom cherché.
2. Recherche dichotomique : ouvrir l'annuaire au milieu, si le nom qui s'y trouve est plus loin alphabétiquement que le nom cherché, regarder avant, sinon, regarder après. Refaire l'opération qui consiste à couper les demi-annuaires (puis les quarts d'annuaires, puis les huitièmes d'annuaires, etc.) jusqu'à trouver le nom cherché.

Pour chacune de ces méthodes il existe un pire des cas et un meilleur des cas. Prenons la méthode 1 :

• Le meilleur des cas est celui où le nom est le premier dans l'annuaire, le nom est alors trouvé instantanément.
• Le pire des cas est celui où le nom est le dernier dans l'annuaire, le nom est alors trouvé après avoir parcouru tous les noms.

Si l'annuaire contient 30 000 noms, le pire cas demandera 30 000 étapes. La complexité dans le pire des cas de cette première méthode pour ${\displaystyle n}$ entrées dans l'annuaire fourni est ${\displaystyle {\mathcal {O}}(n)}$, cela signifie que dans le pire des cas, le temps de calcul est de l'ordre de grandeur de ${\displaystyle n}$ : il faut parcourir tous les ${\displaystyle n}$ noms une fois.

Le second algorithme demandera dans le pire des cas de séparer en deux l'annuaire, puis de séparer à nouveau cette sous-partie en deux, ainsi de suite jusqu'à n'avoir qu'un seul nom. Le nombre d'étapes nécessaire sera le nombre entier qui est immédiatement plus grand que ${\displaystyle \log _{2}\,n}$ qui, quand ${\displaystyle n}$ est 30 000, est 15 (car ${\displaystyle 2^{15}}$ vaut 32 768). La complexité (le nombre d'opérations) de ce second algorithme dans le pire des cas est alors ${\displaystyle {\mathcal {O}}(\log _{2}\,n)}$, ce qui veut dire que l'ordre de grandeur du nombre d'opérations de ce pire cas est le logarithme en base ${\displaystyle 2}$ de la taille de l'annuaire, c'est-à-dire que pour un annuaire dont la taille est comprise entre ${\displaystyle 2^{p-1}}$ et ${\displaystyle 2^{p}}$, il sera de l'ordre de ${\displaystyle p}$. On peut écrire aussi bien ${\displaystyle {\mathcal {O}}(\ln \,n)}$ ou ${\displaystyle {\mathcal {O}}(\log _{2}\,n)}$, car ${\displaystyle \ln \,n}$ et ${\displaystyle \log _{2}\,n}$ ont le même ordre de grandeur.

Cette section ne cite aucune source et peut contenir des informations erronées (signalé en avril 2025).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

Trouver des sources sur « Analyse de la complexité des algorithmes » :

• Archive Wikiwix
• Bing
• Cairn
• DuckDuckGo
• E. Universalis
• Gallica
• Google
• G. Books
• G. News
• G. Scholar
• Persée
• Qwant
• (zh) Baidu
• (ru) Yandex
• (wd) trouver des œuvres sur Wikidata

Pour donner un ordre d'idée sur les différentes complexités, le tableau ci-dessous présente les différentes classes de complexité, leur nom, des temps d'exécution de référence et un problème de ladite complexité. Les temps d'exécution sont estimés sur la base d'un accès mémoire de 10 nanosecondes par étape. Les temps présentés ici n'ont aucune valeur réaliste, car lors d'une exécution sur machine de nombreux mécanismes entrent en jeu. Les temps sont donnés à titre indicatif pour fournir un ordre de grandeur sur le temps nécessaire à l'exécution de tel ou tel algorithme.

Ordre de grandeur du temps nécessaire à l'exécution d'un algorithme d'un type de complexité

Temps	Type de complexité	Temps pour n = 1	Temps pour n = 5	Temps pour n = 10	Temps pour n = 20	Temps pour n = 50	Temps pour n = 250	Temps pour n = 1 000	Temps pour n = 10 000	Temps pour n = 1 000 000	Problème exemple
${\displaystyle \Theta (1)}$	complexité constante	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	accès à une cellule de tableau
${\displaystyle \Theta (\log(n))}$	complexité logarithmique	10 ns	10 ns	10 ns	10 ns	20 ns	30 ns	30 ns	40 ns	60 ns	recherche dichotomique
${\displaystyle \Theta ({\sqrt {n}})}$	complexité racinaire	10 ns	22 ns	32 ns	45 ns	71 ns	158 ns	316 ns	1 µs	10 µs	test de primalité naïf
${\displaystyle \Theta (n)}$	complexité linéaire	10 ns	50 ns	100 ns	200 ns	500 ns	2.5 µs	10 µs	100 µs	10 ms	parcours de liste
${\displaystyle \Theta (n\times log^{*}(n))}$	complexité quasi linéaire	10 ns	50 ns	100 ns	200 ns	501 ns	2.5 µs	10 µs	100,5 µs	10,05 ms	triangulation de Delaunay
${\displaystyle \Theta (n\log(n))}$	complexité linéarithmique	10 ns	40 ns	100 ns	260 ns	850 ns	6 µs	30 µs	400 µs	60 ms	tris par comparaisons optimaux (comme le tri fusion ou le tri par tas)
${\displaystyle \Theta (n^{2})}$	complexité quadratique (polynomiale)	100ns	250 ns	1 µs	4 µs	25 µs	625 µs	10 ms	1 s	2.8 heures	parcours de tableaux 2D
${\displaystyle \Theta (n^{3})}$	complexité cubique (polynomiale)	1 µs	1.25 µs	10 µs	80 µs	1.25 ms	156 ms	10 s	2.7 heures	316 ans	multiplication matricielle naïve
${\displaystyle \Theta (2^{\rm {{poly}(\log(n))}})}$	complexité sous-exponentielle	10ns	30 ns	100 ns	492 ns	7 µs	5 ms	10 s	3.2 ans	${\displaystyle 10^{20}}$ ans	factorisation d’entiers avec GNFS (le meilleur algorithme connu en 2018)
${\displaystyle \Theta (2^{\rm {{poly}(n)}})}$	complexité exponentielle	20ns	320 ns	10 µs	10 ms	130 jours	${\displaystyle 10^{59}}$ ans	...	...	...	problème du sac à dos par force brute
${\displaystyle \Theta (n!)}$	complexité factorielle	10ns	1.2 µs	36 ms	771 ans	${\displaystyle 10^{48}}$ ans	...	...	...	...	problème du voyageur de commerce avec une approche naïve
${\displaystyle \Theta (2^{2^{\rm {{poly}(n)}}})}$	complexité doublement exponentielle	400 ns	4.3 s	${\displaystyle 10^{278}}$ ans	...	...	...	...	...	...	décision de l'arithmétique de Presburger

${\displaystyle log^{*}(n)}$ est le logarithme itéré.

• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
• (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7)
• (en) Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1993 (ISBN 978-0-201-53082-7)
• (en) Michael R. Garey et David S. Johnson, Computers and Intractability : A guide to the theory of NP-completeness, W.H. Freeman & Company, 1979 (ISBN 0-7167-1045-5)
• Richard Lassaigne et Michel de Rougemont, Logique et Complexité, Hermes, 1996 (ISBN 2-86601-496-0)
• Nicolas Hermann et Pierre Lescanne, Est-ce que P = NP ? Les Dossiers de La Recherche, 20:64–68, août-octobre 2005

• Théorie de la complexité (informatique théorique)
• Complexité, article général sur la complexité
• Complexité de Kolmogorov
• Explosion combinatoire
• Machine de Turing non déterministe
• Réduction polynomiale

• Portail de l’informatique
• Portail de l'informatique théorique