Complexité temporelle

En informatique théorique , la complexité temporelle désigne la complexité de calcul qui décrit le temps d'exécution d'un algorithme . Elle est généralement estimée en comptant le nombre d'opérations élémentaires effectuées par l'algorithme, en supposant que chaque opération élémentaire a une durée d'exécution fixe. Ainsi, la durée d'exécution et le nombre d'opérations élémentaires sont liés par un facteur constant .

Comme le temps d'exécution d'un algorithme peut varier pour des entrées de même taille, on considère généralement sa complexité temporelle dans le pire des cas , c'est-à-dire le temps maximal requis pour des entrées d'une taille donnée. Moins courante, et généralement spécifiée explicitement, est la complexité temporelle moyenne , qui correspond au temps moyen d'exécution pour des entrées de taille donnée (ce qui est logique puisqu'il n'existe qu'un nombre fini d'entrées possibles de cette taille). Dans les deux cas, la complexité temporelle est généralement exprimée en fonction de la taille de l'entrée. Cette fonction étant généralement difficile à calculer exactement, et le temps d'exécution pour les petites entrées étant généralement négligeable, on s'intéresse généralement au comportement de la complexité lorsque la taille de l'entrée augmente, c'est-à-dire à son comportement asymptotique . Par conséquent, la complexité temporelle est généralement exprimée à l'aide de la notation grand O , typiquement O(n) , O(n- n), O(n-n), O(n-n ), etc. , où n est la taille, en bits , de l'entrée. ${\displaystyle O(n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n)}</annotation></semantics></math><img src=$ ${\displaystyle O(n\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log n)}</annotation></semantics></math><img src=$ ${\displaystyle O(n^{\alpha }) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mi>α</mi></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n^{\alpha })}</annotation></semantics></math><img src=$ ${\displaystyle O(2^{n}) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mn>2</mn><mrow><mi>n</mi></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(2^{n})}</annotation></semantics></math><img src=$

La complexité des algorithmes est classée selon le type de fonction apparaissant dans la notation grand O. Par exemple, un algorithme de complexité temporelle O(n) est un algorithme linéaire , et un algorithme de complexité temporelle O(n) = n/2 pour une certaine constante est un algorithme polynomial . ${\displaystyle O(n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n)}</annotation></semantics></math><img src=$ ${\displaystyle O(n^{\alpha }) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mi>α</mi></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n^{\alpha })}</annotation></semantics></math><img src=$ $0 α > 0$ 0

Tableau des complexités temporelles courantes

Le tableau suivant résume certaines classes de complexités temporelles couramment rencontrées. Dans le tableau, poly( x ) = x ^{O (1)} , c'est-à-dire polynôme en x .

Un algorithme est dit à temps constant (souvent représenté par `t`) lorsque sa fonction de complexité est bornée par une valeur qui ne varie pas avec la taille des données d'entrée. Cela signifie que le temps d'exécution reste constant quelle que soit la quantité de données traitées. Par exemple, accéder à un élément spécifique d'un tableau est une opération à temps constant, car elle ne nécessite qu'une seule opération pour localiser cet élément. ${ extstyle O(1) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo></mstyle></mrow><annotation>{ extstyle O(1)}</annotation></semantics></math><img src=$ ${ extstyle T(n) <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{ extstyle T(n)}</annotation></semantics></math><img src=$

En revanche, la détermination de la valeur minimale dans un tableau non ordonné ne s'effectue pas en temps constant ; elle nécessite l'examen de chaque élément , ce qui donne une complexité temporelle linéaire, ou O( n). Cependant, si le nombre d'éléments est connu et fixe, certaines tâches peuvent encore être considérées comme s'effectuant en temps constant. ${ extstyle O(n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{ extstyle O(n)}</annotation></semantics></math><img src=$

Il est important de noter que le terme « temps constant » ne signifie pas que le temps d'exécution doit être totalement indépendant de la taille du problème ; il doit plutôt présenter une limite supérieure constante, quelle que soit la taille des données d'entrée. Par exemple, une tâche consistant à échanger les valeurs de a et b pour garantir que la condition soit remplie est classée comme ayant un temps constant, même si le temps d'exécution peut varier selon que la condition est déjà remplie ou non. L'essentiel est qu'il existe une constante t telle que le temps d'exécution ne dépasse jamais t , quelles que soient les valeurs des données d'entrée. ${ extstyle a\leq b <semantics><mrow><mstyle><mi>a</mi><mo>≤</mo><mi>b</mi></mstyle></mrow><annotation>{ extstyle a\leq b}</annotation></semantics></math><img src=$

Les algorithmes à temps d'exécution constant sont particulièrement importants dans des domaines comme la cryptographie, où les attaques temporelles peuvent exploiter les variations du temps d'exécution. En concevant des algorithmes à temps d'exécution constant, les développeurs peuvent renforcer la sécurité et garantir la prévisibilité des performances, ce qui en fait un critère fondamental en génie logiciel.

temps logarithmique

On dit qu'un algorithme s'exécute en temps logarithmique lorsque . Puisque et sont liés par un multiplicateur constant , et que ce multiplicateur est sans incidence sur la classification grand O, l'usage standard pour les algorithmes en temps logarithmique est indépendamment de la base du logarithme apparaissant dans l'expression de T . ${\displaystyle T(n)=O(\log n) <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>n</mi><mo>)</mo><mo>=</mo><mi>O</mi><mo>(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle T(n)=O(\log n)}</annotation></semantics></math><img src=$ ${\displaystyle \log _{a}n <semantics><mrow><mstyle><msub><mi>log</mi><mrow><mi>a</mi></mrow></msub><mo>⁡</mo><mi>n</mi></mstyle></mrow><annotation>{\displaystyle \log _{a}n}</annotation></semantics></math><img src=$ ${\displaystyle \log _{b}n <semantics><mrow><mstyle><msub><mi>log</mi><mrow><mi>b</mi></mrow></msub><mo>⁡</mo><mi>n</mi></mstyle></mrow><annotation>{\displaystyle \log _{b}n}</annotation></semantics></math><img src=$ ${\displaystyle O(\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(\log n)}</annotation></semantics></math><img src=$

Les algorithmes s'exécutant en temps logarithmique sont couramment rencontrés dans les opérations sur les arbres binaires ou lors de l'utilisation de la recherche binaire .

Un algorithme est considéré comme très efficace lorsque le rapport entre le nombre d'opérations et la taille de l'entrée diminue et tend vers zéro lorsque n augmente. Un algorithme qui doit accéder à tous les éléments de son entrée ne peut pas s'exécuter en temps logarithmique, car le temps nécessaire pour lire une entrée de taille n est de l'ordre de n² . ${\displaystyle O(\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(\log n)}</annotation></semantics></math><img src=$

Un exemple de complexité logarithmique est donné par la recherche dans un dictionnaire. Considérons un dictionnaire D contenant n entrées, triées par ordre alphabétique . Supposons que, pour tout n ≥ 0 , on puisse accéder à la k -ième entrée du dictionnaire en un temps constant. Notons cette k -ième entrée. Sous ces hypothèses, le test permettant de vérifier si un mot w est présent dans le dictionnaire peut être effectué en temps logarithmique : considérons w = wk , où ∅ désigne la fonction partie entière . Si w ≥ w (c’est-à-dire si le mot w se trouve exactement au milieu du dictionnaire), la recherche est terminée. Sinon, si w est antérieur au mot central du dictionnaire dans l’ordre alphabétique, on poursuit la recherche de la même manière dans la moitié gauche (c’est-à-dire la moitié antérieure) du dictionnaire, et ce, de façon répétée jusqu’à trouver le mot. Enfin, si w est postérieur au mot central, on poursuit la recherche de la même manière dans la moitié droite du dictionnaire. Cet algorithme est similaire à la méthode souvent utilisée pour trouver une entrée dans un dictionnaire papier. Par conséquent, l'espace de recherche au sein du dictionnaire diminue à mesure que l'algorithme se rapproche du mot cible. ${\displaystyle 1\leq k\leq n <semantics><mrow><mstyle><mn>1</mn><mo>≤</mo><mi>k</mi><mo>≤</mo><mi>n</mi></mstyle></mrow><annotation>{\displaystyle 1\leq k\leq n}</annotation></semantics></math><img src=$ ${\displaystyle D(k) <semantics><mrow><mstyle><mi>D</mi><mo>(</mo><mi>k</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle D(k)}</annotation></semantics></math><img src=$ ${\displaystyle D\left(\left\lfloor {\frac {n}{2}} ight floor ight) <semantics><mrow><mstyle><mi>D</mi><mrow><mo>(</mo><mrow><mo>⌊</mo><mrow><mfrac><mi>n</mi><mn>2</mn></mfrac></mrow><mo>⌋</mo></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle D\left(\left\lfloor {\frac {n}{2}} ight floor ight)}</annotation></semantics></math><img src=$ ${\displaystyle \lfloor \; floor <semantics><mrow><mstyle><mo>⌊</mo><mspace></mspace><mo>⌋</mo></mstyle></mrow><annotation>{\displaystyle \lfloor \; floor }</annotation></semantics></math><img src=$ ${\displaystyle w=D\left(\left\lfloor {\frac {n}{2}} ight floor ight) <semantics><mrow><mstyle><mi>w</mi><mo>=</mo><mi>D</mi><mrow><mo>(</mo><mrow><mo>⌊</mo><mrow><mfrac><mi>n</mi><mn>2</mn></mfrac></mrow><mo>⌋</mo></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle w=D\left(\left\lfloor {\frac {n}{2}} ight floor ight)}</annotation></semantics></math><img src=$ ${\displaystyle w<D\left(\left\lfloor {\frac {n}{2}} ight floor ight) <semantics><mrow><mstyle><mi>w</mi><mo><</mo><mi>D</mi><mrow><mo>(</mo><mrow><mo>⌊</mo><mrow><mfrac><mi>n</mi><mn>2</mn></mfrac></mrow><mo>⌋</mo></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle w<D\left(\left\lfloor {\frac {n}{2}} ight floor ight)}</annotation></semantics></math><img src=$

temps polylogarithmique

On dit qu'un algorithme s'exécute en temps polylogarithmique si son temps est de l'ordre de k pour une certaine constante k . Une autre façon d'écrire cela est : ${\displaystyle T(n) <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle T(n)}</annotation></semantics></math><img src=$ ${\displaystyle O{\bigl (}(\log n)^{k}{\bigr ) <semantics><mrow><mstyle><mi>O</mi><mrow><mrow><mo>(</mo></mrow></mrow><mo>(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><msup><mo>)</mo><mrow><mi>k</mi></mrow></msup><mrow><mrow><mo>)</mo></mrow></mrow></mstyle></mrow><annotation>{\displaystyle O{\bigl (}(\log n)^{k}{\bigr )}}</annotation></semantics></math><img src=$ ${\displaystyle O(\log ^{k}n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>log</mi><mrow><mi>k</mi></mrow></msup><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(\log ^{k}n)}</annotation></semantics></math><img src=$

Par exemple, l'ordonnancement de chaînes de matrices peut être résolu en temps polylogarithmique sur une machine à accès aléatoire parallèle , et un graphe peut être déterminé comme étant planaire de manière entièrement dynamique en temps par opération d'insertion/suppression. ${\displaystyle O(\log ^{3}n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>log</mi><mrow><mn>3</mn></mrow></msup><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(\log ^{3}n)}</annotation></semantics></math><img src=$

Temps sous-linéaire

On dit qu'un algorithme s'exécute en temps sous-linéaire (souvent orthographié temps sublinéaire ) si . Cela inclut notamment les algorithmes dont la complexité temporelle est définie ci-dessus. ${\displaystyle T(n)=o(n) <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>n</mi><mo>)</mo><mo>=</mo><mi>o</mi><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle T(n)=o(n)}</annotation></semantics></math><img src=$

Le terme spécifique d'algorithme en temps sous-linéaire fait généralement référence à des algorithmes randomisés qui échantillonnent une petite fraction de leurs entrées et les traitent efficacement pour inférer approximativement les propriétés de l'instance entière. Ce type d'algorithme en temps sous-linéaire est étroitement lié aux tests de propriétés et aux statistiques .

Voici d'autres contextes dans lesquels les algorithmes peuvent s'exécuter en temps sous-linéaire :

Les algorithmes parallèles qui ont un travail total linéaire ou supérieur (leur permettant de lire l'intégralité de l'entrée), mais une profondeur sous-linéaire .
Les algorithmes qui reposent sur des hypothèses garanties concernant la structure des données d'entrée en sont un exemple important. Les opérations sur les structures de données , comme la recherche binaire dans un tableau trié, en sont un exemple significatif.
Les algorithmes qui recherchent une structure locale dans les données d'entrée, par exemple la recherche d'un minimum local dans un tableau unidimensionnel (peuvent être résolus en temps constant à l'aide d'une variante de la recherche binaire), sont étroitement liés à la notion d' algorithmes de calcul local (ACL). Dans ce cadre, l'algorithme reçoit une entrée volumineuse et interroge des informations locales concernant une sortie valide de grande taille. ${\displaystyle O(\log(n)) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>log</mi><mo>⁡</mo><mo>(</mo><mi>n</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(\log(n))}</annotation></semantics></math><img src=$

Temps linéaire

On dit qu'un algorithme s'exécute en temps linéaire (ou temps O(n)) si sa complexité temporelle est O(n) . Autrement dit, le temps d'exécution augmente au plus linéairement avec la taille de l'entrée. Plus précisément, cela signifie qu'il existe une constante c telle que le temps d'exécution soit au plus O(n) pour toute entrée de taille n . Par exemple, une procédure qui additionne tous les éléments d'une liste s'exécute en un temps proportionnel à la longueur de la liste si le temps d'addition est constant, ou du moins borné par une constante. ${\displaystyle O(n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n)}</annotation></semantics></math><img src=$ ${\displaystyle O(n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n)}</annotation></semantics></math><img src=$ ${\displaystyle cn <semantics><mrow><mstyle><mi>c</mi><mi>n</mi></mstyle></mrow><annotation>{\displaystyle cn}</annotation></semantics></math><img src=$

Le temps linéaire représente la meilleure complexité temporelle possible lorsque l'algorithme doit lire séquentiellement l'intégralité de ses données d'entrée. De nombreuses recherches ont donc été menées pour découvrir des algorithmes présentant un temps d'exécution linéaire, ou du moins quasi linéaire. Ces recherches portent sur des méthodes logicielles et matérielles. Plusieurs technologies matérielles exploitent le parallélisme pour y parvenir. La mémoire adressable par contenu (CAM) en est un exemple . Ce concept de temps linéaire est utilisé dans les algorithmes de recherche de chaînes de caractères, tels que l' algorithme de Boyer-Moore et l'algorithme d'Ukkonen .

Temps quasi-linéaire

On dit qu'un algorithme s'exécute en temps quasi-linéaire (ou log-linéaire ) si, pour une certaine constante positive k ; le temps linéaire-ithmique est le cas . En utilisant la notation O souple, ces algorithmes sont . Les algorithmes en temps quasi-linéaire sont également pour toute constante et s'exécutent donc plus rapidement que tout algorithme en temps polynomial dont la borne temporelle inclut un terme pour tout . ${\displaystyle T(n)=O(n\log ^{k}n) <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>n</mi><mo>)</mo><mo>=</mo><mi>O</mi><mo>(</mo><mi>n</mi><msup><mi>log</mi><mrow><mi>k</mi></mrow></msup><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle T(n)=O(n\log ^{k}n)}</annotation></semantics></math><img src=$ ${\displaystyle k=1 <semantics><mrow><mstyle><mi>k</mi><mo>=</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle k=1}</annotation></semantics></math><img src=$ ${\displaystyle { ilde {O}}(n) <semantics><mrow><mstyle><mrow><mrow><mover><mi>O</mi><mo>~</mo></mover></mrow></mrow><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle { ilde {O}}(n)}</annotation></semantics></math><img src=$ ${\displaystyle O(n^{1+\varepsilon }) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mn>1</mn><mo>+</mo><mi>ε</mi></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n^{1+\varepsilon })}</annotation></semantics></math><img src=$ $0 ε > 0$ 0 ${\displaystyle n^{c <semantics><mrow><mstyle><msup><mi>n</mi><mrow><mi>c</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle n^{c}}</annotation></semantics></math><img src=$ $1 c > 1$ 1

Les algorithmes qui s'exécutent en temps quasi-linéaire comprennent :

Tri fusion sur place , ${\displaystyle O(n\log ^{2}n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><msup><mi>log</mi><mrow><mn>2</mn></mrow></msup><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log ^{2}n)}</annotation></semantics></math><img src=$
L'algorithme Quicksort , dans sa version randomisée, a un temps d'exécution moyen pour les entrées les plus défavorables. Sa version non randomisée a un temps d'exécution moyen uniquement en considérant la complexité moyenne. ${\displaystyle O(n\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log n)}</annotation></semantics></math><img src=$ ${\displaystyle O(n\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log n)}</annotation></semantics></math><img src=$ ${\displaystyle O(n\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log n)}</annotation></semantics></math><img src=$
Tri par tas , tri fusion , tri intro , tri par arbre binaire, tri lisse , tri patient , etc. dans le pire des cas ${\displaystyle O(n\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log n)}</annotation></semantics></math><img src=$
Transformées de Fourier rapides , ${\displaystyle O(n\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log n)}</annotation></semantics></math><img src=$
calcul de tableau de Monge , ${\displaystyle O(n\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log n)}</annotation></semantics></math><img src=$
Algorithme de Schönhage – Strassen pour la multiplication , ${\displaystyle O(n\log n\log \log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log n\log \log n)}</annotation></semantics></math><img src=$

Dans de nombreux cas, le temps d'exécution correspond simplement au nombre d' opérations effectuées n fois (pour la notation, voir la notation Big O § Famille des notations de Bachmann-Landau ). Par exemple, le tri par arbre binaire crée un arbre binaire en insérant successivement chaque élément d'un tableau de taille n . Puisque l'opération d'insertion dans un arbre binaire de recherche auto-équilibré a une durée O(n log n), l'algorithme complet a une durée O(n log n). ${\displaystyle O(n\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log n)}</annotation></semantics></math><img src=$ ${\displaystyle \Theta (\log n) <semantics><mrow><mstyle><mi>Θ</mi><mo>(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \Theta (\log n)}</annotation></semantics></math><img src=$ ${\displaystyle O(\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(\log n)}</annotation></semantics></math><img src=$ ${\displaystyle O(n\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log n)}</annotation></semantics></math><img src=$

Les tris par comparaison nécessitent au moins comparaisons dans le pire des cas car , d'après l'approximation de Stirling , . Ils résultent également fréquemment de la relation de récurrence . ${\displaystyle \Omega (n\log n) <semantics><mrow><mstyle><mi>Ω</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \Omega (n\log n)}</annotation></semantics></math><img src=$ ${\displaystyle \log(n!)=\Theta (n\log n) <semantics><mrow><mstyle><mi>log</mi><mo>⁡</mo><mo>(</mo><mi>n</mi><mo>!</mo><mo>)</mo><mo>=</mo><mi>Θ</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \log(n!)=\Theta (n\log n)}</annotation></semantics></math><img src=$ ${ extstyle T(n)=2T\left({\frac {n}{2}} ight)+O(n) <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>n</mi><mo>)</mo><mo>=</mo><mn>2</mn><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mi>n</mi><mn>2</mn></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{ extstyle T(n)=2T\left({\frac {n}{2}} ight)+O(n)}</annotation></semantics></math><img src=$

Temps sous-quadratique

On dit qu'un algorithme a un temps sous-quadratique si . ${\displaystyle T(n)=o(n^{2}) <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>n</mi><mo>)</mo><mo>=</mo><mi>o</mi><mo>(</mo><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle T(n)=o(n^{2})}</annotation></semantics></math><img src=$

Par exemple, les algorithmes de tri simples, basés sur la comparaison, ont une complexité quadratique (comme le tri par insertion ), tandis que des algorithmes plus avancés ont une complexité sous-quadratique (comme le tri Shell ). Aucun algorithme de tri général ne s'exécute en temps linéaire, mais le passage d'une complexité quadratique à une complexité sous-quadratique revêt une grande importance pratique.

temps polynomial

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, that is, T(n) = O(n^k) for some positive constant k.Problems for which a deterministic polynomial-time algorithm exists belong to the complexity classP, which is central in the field of computational complexity theory. Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".

Some examples of polynomial-time algorithms:

The selection sort sorting algorithm on n integers performs ${\displaystyle An^{2 <semantics><mrow><mstyle><mi>A</mi><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup></mstyle></mrow><annotation>{\displaystyle An^{2}}</annotation></semantics></math><img src=$ A. Thus it runs in time ${\displaystyle O(n^{2}) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n^{2})}</annotation></semantics></math><img src=$
All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.
Maximum matchings in graphs can be found in polynomial time. In some contexts, especially in optimization, one differentiates between strongly polynomial time and weakly polynomial time algorithms.

These two concepts are only relevant if the inputs to the algorithms consist of integers.

Complexity classes

The concept of polynomial time leads to several complexity classes in computational complexity theory. Some important classes defined using polynomial time are the following.

P: The complexity class of decision problems that can be solved on a deterministic Turing machine in polynomial time
NP: The complexity class of decision problems that can be solved on a non-deterministic Turing machine in polynomial time
ZPP: The complexity class of decision problems that can be solved with zero error on a probabilistic Turing machine in polynomial time
RP: The complexity class of decision problems that can be solved with 1-sided error on a probabilistic Turing machine in polynomial time.
BPP: The complexity class of decision problems that can be solved with 2-sided error on a probabilistic Turing machine in polynomial time
BQP : Classe de complexité des problèmes de décision pouvant être résolus avec une erreur bilatérale sur une machine de Turing quantique en temps polynomial

P désigne la classe de complexité temporelle minimale sur une machine déterministe, robuste aux changements de modèle de machine. (Par exemple, le passage d'une machine de Turing à une seule bande à une machine à plusieurs bandes peut entraîner un gain de vitesse quadratique, mais tout algorithme s'exécutant en temps polynomial sur un modèle s'exécute également en temps polynomial sur l'autre.) Chaque machine abstraite possède une classe de complexité correspondant aux problèmes résolubles en temps polynomial sur cette machine.

temps superpolynomial

Un algorithme est défini comme prenant un temps superpolynomial si T ( n ) n'est pas borné supérieurement par un polynôme ; c'est-à-dire si ⁠ ⁠ ${\displaystyle T(n) ot \in O(n^{c}) <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>n</mi><mo>)</mo><mo>∉</mo><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mi>c</mi></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle T(n) ot \in O(n^{c})}</annotation></semantics></math><img src=$ pour tout entier positif c .

Par exemple, un algorithme qui s'exécute en 2 ⁿ étapes sur une entrée de taille n nécessite un temps superpolynomial (plus précisément, un temps exponentiel).

Un algorithme utilisant des ressources exponentielles est clairement superpolynomial, mais certains algorithmes ne le sont que très faiblement. Par exemple, le test de primalité d'Adleman-Pomerance-Rumely s'exécute en un temps O ^{(log log}ⁿ⁾ pour des entrées de n bits ; sa complexité croît plus rapidement que celle de ⁿ pour des valeurs de n suffisamment grandes , mais la taille des entrées doit devenir excessivement grande pour ne plus pouvoir être dominée par un polynôme de petit degré.

Un algorithme dont le temps d'exécution est superpolynomial n'appartient pas à la classe de complexité P. La thèse de Cobham postule que ces algorithmes sont impraticables, ce qui est souvent le cas. Le problème P versus NP n'étant pas résolu, on ignore si les problèmes NP-complets nécessitent un temps d'exécution superpolynomial.

temps quasi-polynomial

Les algorithmes quasi-polynomiaux sont des algorithmes dont le temps d'exécution présente une croissance quasi-polynomiale , un comportement qui peut être plus lent qu'un temps polynomial mais nettement plus rapide qu'un temps exponentiel . Le temps d'exécution dans le pire des cas d'un algorithme quasi-polynomial est O(n^2) pour une valeur de n fixée . Lorsque n = 0, le temps d'exécution est polynomial, et pour n = 0, il est sous-linéaire. ${\displaystyle 2^{O(\log ^{c}n) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mi>O</mi><mo>(</mo><msup><mi>log</mi><mrow><mi>c</mi></mrow></msup><mo>⁡</mo><mi>n</mi><mo>)</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{O(\log ^{c}n)}}</annotation></semantics></math><img src=$ $0 c > 0$ 0 ${\displaystyle c=1 <semantics><mrow><mstyle><mi>c</mi><mo>=</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle c=1}</annotation></semantics></math><img src=$ ${\displaystyle c<1 <semantics><mrow><mstyle><mi>c</mi><mo><</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle c<1}</annotation></semantics></math><img src=$

Il existe des problèmes pour lesquels on connaît des algorithmes quasi-polynomiaux, mais aucun algorithme polynomial. De tels problèmes apparaissent dans les algorithmes d'approximation ; un exemple célèbre est le problème de l'arbre de Steiner orienté , pour lequel il existe un algorithme d'approximation quasi-polynomial atteignant un facteur d'approximation de ( n étant le nombre de sommets), mais démontrer l'existence d'un tel algorithme polynomial reste un problème ouvert. ${\displaystyle O(\log ^{3}n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>log</mi><mrow><mn>3</mn></mrow></msup><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(\log ^{3}n)}</annotation></semantics></math><img src=$

Parmi les autres problèmes de calcul admettant des solutions en temps quasi-polynomial mais aucune solution en temps polynomial connue, on peut citer le problème de la clique plantée, dont le but est de trouver une grande clique dans l'union d'une clique et d'un graphe aléatoire . Bien que résoluble en temps quasi-polynomial, il a été conjecturé que le problème de la clique plantée n'admet pas de solution en temps polynomial ; cette conjecture a été utilisée comme hypothèse de complexité pour démontrer la difficulté de plusieurs autres problèmes en théorie des jeux computationnelle , en vérification de propriétés et en apprentissage automatique .

La classe de complexité QP regroupe tous les problèmes qui admettent des algorithmes en temps quasi-polynomial. Elle peut être définie en termes de DTIME comme suit.

{\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n} ight) <semantics><mrow><mstyle><mrow><mstyle><mtext>QP</mtext></mstyle></mrow><mo>=</mo><munder><mo>⋃</mo><mrow><mi>c</mi><mo>∈</mo><mrow><mi>N</mi></mrow></mrow></munder><mrow><mstyle><mtext>DTIME</mtext></mstyle></mrow><mrow><mo>(</mo><msup><mn>2</mn><mrow><msup><mi>log</mi><mrow><mi>c</mi></mrow></msup><mo>⁡</mo><mi>n</mi></mrow></msup><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle {\mbox{QP}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{\log ^{c}n} ight)}</annotation></semantics></math></span><img src=

Lien avec les problèmes NP-complets

En théorie de la complexité, le problème non résolu P versus NP consiste à déterminer si tous les problèmes NP admettent des algorithmes en temps polynomial. Tous les algorithmes les plus connus pour les problèmes NP-complets, comme 3SAT, ont une complexité exponentielle. De fait, on conjecture que de nombreux problèmes NP-complets naturels n'admettent pas d'algorithmes en temps sous-exponentiel. Ici, « temps sous-exponentiel » est entendu au sens de la seconde définition présentée ci-dessous. (Par ailleurs, de nombreux problèmes de graphes, représentés naturellement par des matrices d'adjacence, sont résolubles en temps sous-exponentiel simplement parce que la taille de l'entrée est le carré du nombre de sommets.) Cette conjecture (pour le problème k-SAT) est connue sous le nom d' hypothèse du temps exponentiel . Puisqu'il est conjecturé que les problèmes NP-complets n'admettent pas d'algorithmes en temps quasi-polynomial, certains résultats d'inapproximabilité dans le domaine des algorithmes d'approximation reposent sur cette conjecture. Voir par exemple les résultats d'inapproximabilité connus pour le problème de la couverture d'ensembles .

Temps sous-exponentiel

Le terme « temps sous-exponentiel » est utilisé pour exprimer que le temps d'exécution d'un algorithme peut croître plus rapidement que n'importe quel polynôme, tout en restant nettement inférieur à celui d'une exponentielle. En ce sens, les problèmes admettant des algorithmes à temps sous-exponentiel sont plus faciles à résoudre que ceux ne disposant que d'algorithmes exponentiels. La définition précise de « sous-exponentiel » ne fait pas consensus , mais les deux définitions les plus couramment utilisées sont présentées ci-dessous.

Première définition

Un problème est dit sous-exponentiel s'il peut être résolu en un temps d'exécution dont le logarithme est inférieur à la somme des carrés de tout polynôme donné. Plus précisément, un problème est sous-exponentiel s'il existe, pour tout ^{^ε} > 0, un algorithme qui le résout en un temps O ( 2nε ) ^. L'ensemble de tous ces problèmes constitue la classe de complexité SUBEXP , qui peut être définie en fonction de DTIME comme suit.

0}{ extsf {DTIME}}\left(2^{n^{\varepsilon }} ight) SUBEXP = ⋂_{ε > 0} DTIME (2^{n^{ε}})

0}{ extsf {DTIME}}\left(2^{n^{\varepsilon }} ight)

Cette notion de sous-exponentielle n'est pas uniforme en termes de ε dans le sens où ε ne fait pas partie de l'entrée et chaque ε peut avoir son propre algorithme pour le problème.

Deuxième définition

Certains auteurs définissent le temps sous-exponentiel comme un temps d'exécution en O(n^n) . Cette définition autorise des temps d'exécution plus longs que la première définition du temps sous-exponentiel. Un exemple d'algorithme sous-exponentiel est l'algorithme classique le plus connu pour la factorisation d'entiers, le crible généralisé , qui s'exécute en O(n^n) , où n est la longueur de l'entrée . Un autre exemple est le problème d'isomorphisme de graphes , résolu en O(n^n ) par le meilleur algorithme connu de 1982 à 2016. Cependant, lors de la conférence STOC 2016, un algorithme quasi-polynomial a été présenté. ${\displaystyle 2^{o(n) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mi>o</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{o(n)}}</annotation></semantics></math><img src=$ ${\displaystyle 2^{{O}(n^{1/3}(\log n)^{2/3}) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mrow><mi>O</mi></mrow><mo>(</mo><msup><mi>n</mi><mrow><mn>1</mn><mrow><mo>/</mo></mrow><mn>3</mn></mrow></msup><mo>(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><msup><mo>)</mo><mrow><mn>2</mn><mrow><mo>/</mo></mrow><mn>3</mn></mrow></msup><mo>)</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{{O}(n^{1/3}(\log n)^{2/3})}}</annotation></semantics></math><img src=$ ${\displaystyle 2^{O\left({\sqrt {n\log n}} ight) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mi>O</mi><mrow><mo>(</mo><mrow><msqrt><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi></msqrt></mrow><mo>)</mo></mrow></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{O\left({\sqrt {n\log n}} ight)}}</annotation></semantics></math><img src=$

Il est important que l'algorithme puisse avoir une complexité sous-exponentielle par rapport à la taille de l'instance, au nombre de sommets ou au nombre d'arêtes. En complexité paramétrée , cette différence est explicitée en considérant des paires de problèmes de décision et de paramètres k . SUBEPT est la classe de tous les problèmes paramétrés dont le temps d'exécution est sous-exponentiel en k et polynomial en la taille de l'entrée n : ${\displaystyle (L,k) <semantics><mrow><mstyle><mo>(</mo><mi>L</mi><mo>,</mo><mi>k</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (L,k)}</annotation></semantics></math><img src=$

{\displaystyle { extsf {SUBEPT}}={ extsf {DTIME}}\left(2^{o(k)}\cdot { extsf {poly}}(n) ight). <semantics><mrow><mstyle><mrow><mrow><mtext>SUBEPT</mtext></mrow></mrow><mo>=</mo><mrow><mrow><mtext>DTIME</mtext></mrow></mrow><mrow><mo>(</mo><mrow><msup><mn>2</mn><mrow><mi>o</mi><mo>(</mo><mi>k</mi><mo>)</mo></mrow></msup><mo>⋅</mo><mrow><mrow><mtext>poly</mtext></mrow></mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow><mo>)</mo></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle { extsf {SUBEPT}}={ extsf {DTIME}}\left(2^{o(k)}\cdot { extsf {poly}}(n) ight).}</annotation></semantics></math></span><img src=

Plus précisément, SUBEPT est la classe de tous les problèmes paramétrés pour lesquels il existe une fonction calculable avec et un algorithme qui décide L en temps . ${\displaystyle (L,k) <semantics><mrow><mstyle><mo>(</mo><mi>L</mi><mo>,</mo><mi>k</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (L,k)}</annotation></semantics></math><img src=$ ${\displaystyle f:\mathbb {N} o \mathbb {N} <semantics><mrow><mstyle><mi>f</mi><mo>:</mo><mrow><mi>N</mi></mrow><mo>→</mo><mrow><mi>N</mi></mrow></mstyle></mrow><annotation>{\displaystyle f:\mathbb {N} o \mathbb {N} }</annotation></semantics></math><img src=$ ${\displaystyle f\in o(k) <semantics><mrow><mstyle><mi>f</mi><mo>∈</mo><mi>o</mi><mo>(</mo><mi>k</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle f\in o(k)}</annotation></semantics></math><img src=$ ${\displaystyle 2^{f(k)}\cdot { extsf {poly}}(n) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mi>f</mi><mo>(</mo><mi>k</mi><mo>)</mo></mrow></msup><mo>⋅</mo><mrow><mrow><mtext>poly</mtext></mrow></mrow><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle 2^{f(k)}\cdot { extsf {poly}}(n)}</annotation></semantics></math><img src=$

Hypothèse du temps exponentiel

L' hypothèse du temps exponentiel ( ETH ) stipule que le problème de satisfaisabilité 3SAT , qui concerne les formules booléennes sous forme normale conjonctive avec au plus trois littéraux par clause et n variables, ne peut être résolu en un temps 2 ^{o ( n )} . Plus précisément, l'hypothèse est qu'il existe une constante absolue c > 0 telle que 3SAT ne puisse être résolu en un temps 2 ^{cn} par aucune machine de Turing déterministe. Avec m désignant le nombre de clauses, l'ETH est équivalente à l'hypothèse que kSAT ne peut être résolu en un temps 2 ^{o ( m )} pour tout entier k ≥ 3. [ hypothèse du temps exponentiel implique P ≠ NP .

Temps exponentiel

Un algorithme est dit à complexité exponentielle si T ( n ) est majoré par 2 n ^{poly( n )} , où poly( n ) est un polynôme en n . Plus formellement, un algorithme est à complexité exponentielle si T ( n ) est majoré par O (2 ^{ ^nk} ) pour une certaine constante k . Les problèmes admettant des algorithmes à complexité exponentielle sur une machine de Turing déterministe forment la classe de complexité connue sous le nom d' EXP .

{\displaystyle { extsf {EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{ extsf {DTIME}}\left(2^{n^{c}} ight) <semantics><mrow><mstyle><mrow><mrow><mtext>EXP</mtext></mrow></mrow><mo>=</mo><munder><mo>⋃</mo><mrow><mi>c</mi><mo>∈</mo><mrow><msub><mi>R</mi><mrow><mo>+</mo></mrow></msub></mrow></mrow></munder><mrow><mrow><mtext>DTIME</mtext></mrow></mrow><mrow><mo>(</mo><msup><mn>2</mn><mrow><msup><mi>n</mi><mrow><mi>c</mi></mrow></msup></mrow></msup><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle { extsf {EXP}}=\bigcup _{c\in \mathbb {R_{+}} }{ extsf {DTIME}}\left(2^{n^{c}} ight)}</annotation></semantics></math></span><img src=

Parfois, le temps exponentiel est utilisé pour désigner des algorithmes qui ont T ( n ) = 2 ^{O ( n )} , où l'exposant est au plus une fonction linéaire de n . Cela donne lieu à la classe de complexité E .

{\displaystyle { extsf {E}}=\bigcup _{c\in \mathbb {N} }{ extsf {DTIME}}\left(2^{cn} ight) <semantics><mrow><mstyle><mrow><mrow><mtext>E</mtext></mrow></mrow><mo>=</mo><munder><mo>⋃</mo><mrow><mi>c</mi><mo>∈</mo><mrow><mi>N</mi></mrow></mrow></munder><mrow><mrow><mtext>DTIME</mtext></mrow></mrow><mrow><mo>(</mo><msup><mn>2</mn><mrow><mi>c</mi><mi>n</mi></mrow></msup><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle { extsf {E}}=\bigcup _{c\in \mathbb {N} }{ extsf {DTIME}}\left(2^{cn} ight)}</annotation></semantics></math></span><img src=

Temps factoriel

Un algorithme est dit en temps factoriel si T(n) est majoré par la fonction factorielle n!. Le temps factoriel est un sous-ensemble du temps exponentiel (EXP) car pour tout n ≥ 0. Cependant, il n'est pas un sous-ensemble de E. ${\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }} ight) <semantics><mrow><mstyle><mi>n</mi><mo>!</mo><mo>≤</mo><msup><mi>n</mi><mrow><mi>n</mi></mrow></msup><mo>=</mo><msup><mn>2</mn><mrow><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi></mrow></msup><mo>=</mo><mi>O</mi><mrow><mo>(</mo><msup><mn>2</mn><mrow><msup><mi>n</mi><mrow><mn>1</mn><mo>+</mo><mi>ϵ</mi></mrow></msup></mrow></msup><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle n!\leq n^{n}=2^{n\log n}=O\left(2^{n^{1+\epsilon }} ight)}</annotation></semantics></math><img src=$ $0 ϵ > 0$ 0

Un exemple d'algorithme s'exécutant en temps factoriel est le tri bogosort , un algorithme de tri notoirement inefficace basé sur la méthode des essais et erreurs . Le tri bogosort trie une liste de n éléments en la mélangeant de manière itérative jusqu'à ce qu'elle soit triée. En moyenne, chaque itération de l'algorithme examine l'un des n ! ordres possibles des n éléments. Si les éléments sont distincts, un seul de ces ordres est retenu. Le tri bogosort est lié au théorème du singe savant .

Temps double exponentiel

Un algorithme est dit à temps double exponentiel si T ( n ) est majoré par 2 ^{2 ^{poly( n )}} , où poly( n ) est un polynôme en n . De tels algorithmes appartiennent à la classe de complexité 2-EXPTIME .

{\displaystyle { extsf {2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{ extsf {DTIME}}\left(2^{2^{n^{c}}} ight) <semantics><mrow><mstyle><mrow><mrow><mtext>2-EXPTIME</mtext></mrow></mrow><mo>=</mo><munder><mo>⋃</mo><mrow><mi>c</mi><mo>∈</mo><mrow><mi>N</mi></mrow></mrow></munder><mrow><mrow><mtext>DTIME</mtext></mrow></mrow><mrow><mo>(</mo><msup><mn>2</mn><mrow><msup><mn>2</mn><mrow><msup><mi>n</mi><mrow><mi>c</mi></mrow></msup></mrow></msup></mrow></msup><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle { extsf {2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{ extsf {DTIME}}\left(2^{2^{n^{c}}} ight)}</annotation></semantics></math></span><img src=

Parmi les algorithmes à complexité double exponentielle bien connus, on peut citer :

Procédures de décision pour l'arithmétique de Presburger
Calcul d'une base de Gröbner (dans le pire des cas )
L'élimination des quantificateurs sur les corps réels fermés prend au moins un temps double exponentiel, et peut être effectuée dans ce temps.

Nom	Classe de complexité	Complexité temporelle ( O ( n ) )	Exemples de durées d'exécution	Exemples d'algorithmes
temps constant		${\displaystyle O(1) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(1)}</annotation></semantics></math></span><img src=$	10	Trouver la valeur médiane dans un tableau trié de nombres. Calculer (−1) ⁿ .
temps d'Ackermann inverse		${\displaystyle O{\bigl (}\alpha (n){\bigr ) <semantics><mrow><mstyle><mi>O</mi><mrow><mrow><mo>(</mo></mrow></mrow><mi>α</mi><mo>(</mo><mi>n</mi><mo>)</mo><mrow><mrow><mo>)</mo></mrow></mrow></mstyle></mrow><annotation>{\displaystyle O{\bigl (}\alpha (n){\bigr )}}</annotation></semantics></math></span><img src=$		Temps amorti par opération en utilisant un ensemble disjoint
temps logarithmique itéré		${\displaystyle O(\log ^{}n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>enregistrer</mi><mrow><mo>∗</mo></mrow></msup><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(\log ^{}n)}</annotation></semantics></math></span><img src=$		Coloration distribuée des cycles
logarithmique		${\displaystyle O(\log \log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>enregistrer</mi><mo>⁡</mo><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(\log \log n)}</annotation></semantics></math></span><img src=$		Temps amorti par opération en utilisant une file d'attente à priorité limitée
temps logarithmique	DLOGTIME	${\displaystyle O(\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(\log n)}</annotation></semantics></math></span><img src=$	${\displaystyle \log n <semantics><mrow><mstyle><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi></mstyle></mrow><annotation>{\displaystyle \log n}</annotation></semantics></math></span><img src=$ ${\displaystyle \log(n^{2}) <semantics><mrow><mstyle><mi>enregistrer</mi><mo>⁡</mo><mo>(</mo><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \log(n^{2})}</annotation></semantics></math></span><img src=$	Recherche binaire
temps polylogarithmique		${\displaystyle { extsf {poly}}(\log n) <semantics><mrow><mstyle><mrow><mrow><mtext>poly</mtext></mrow></mrow><mo>(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle { extsf {poly}}(\log n)}</annotation></semantics></math></span><img src=$	${\displaystyle (\log n)^{2 <semantics><mrow><mstyle><mo>(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mstyle></mrow><annotation>{\displaystyle (\log n)^{2}}</annotation></semantics></math></span><img src=$
puissance fractionnaire		${\displaystyle O(n^{c}) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mi>c</mi></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n^{c})}</annotation></semantics></math></span><img src=$ ${\displaystyle 0<c<1 <semantics><mrow><mstyle><mn>0</mn><mo><</mo><mi>c</mi><mo><</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle 0<c<1}</annotation></semantics></math></span><img src=$	${\displaystyle {\sqrt {n <semantics><mrow><mstyle><mrow><msqrt><mi>n</mi></msqrt></mrow></mstyle></mrow><annotation>{\displaystyle {\sqrt {n}}}</annotation></semantics></math></span><img src=$ ${\displaystyle n^{\frac {2}{3 <semantics><mrow><mstyle><msup><mi>n</mi><mrow><mfrac><mn>2</mn><mn>3</mn></mfrac></mrow></msup></mstyle></mrow><annotation>{\displaystyle n^{\frac {2}{3}}}</annotation></semantics></math></span><img src=$	Recherche de plage dans un arbre k -d
temps linéaire		${\displaystyle O(n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n)}</annotation></semantics></math></span><img src=$	n , ${\displaystyle 2n+5 <semantics><mrow><mstyle><mn>2</mn><mi>n</mi><mo>+</mo><mn>5</mn></mstyle></mrow><annotation>{\displaystyle 2n+5}</annotation></semantics></math></span><img src=$	Recherche du plus petit ou du plus grand élément dans un tableau non trié . Algorithme de Kadane . Recherche linéaire .
"n log-étoile n" temps		${\displaystyle O(n\log ^{}n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><msup><mi>log</mi><mrow><mo>∗</mo></mrow></msup><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log ^{}n)}</annotation></semantics></math></span><img src=$		L'algorithme de triangulation polygonale de Seidel .
temps linéaire-ithmique		${\displaystyle O(n\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n\log n)}</annotation></semantics></math></span><img src=$	${\displaystyle n\log n <semantics><mrow><mstyle><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n\log n}</annotation></semantics></math></span><img src=$ ${\displaystyle \log n! <semantics><mrow><mstyle><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>!</mo></mstyle></mrow><annotation>{\displaystyle \log n!}</annotation></semantics></math></span><img src=$	Tri par comparaison le plus rapide possible . Transformée de Fourier rapide .
temps quasi-linéaire		${\displaystyle n{ extsf {poly}}(\log n) <semantics><mrow><mstyle><mi>n</mi><mrow><mrow><mtext>poly</mtext></mrow></mrow><mo>(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle n{ extsf {poly}}(\log n)}</annotation></semantics></math></span><img src=$	${\displaystyle n\log ^{2}n <semantics><mrow><mstyle><mi>n</mi><msup><mi>log</mi><mrow><mn>2</mn></mrow></msup><mo>⁡</mo><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n\log ^{2}n}</annotation></semantics></math></span><img src=$	Évaluation polynomiale multipoint
temps quadratique		${\displaystyle O(n^{2}) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n^{2})}</annotation></semantics></math></span><img src=$	${\displaystyle n^{2 <semantics><mrow><mstyle><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup></mstyle></mrow><annotation>{\displaystyle n^{2}}</annotation></semantics></math></span><img src=$	Tri à bulles . Tri par insertion . Convolution directe
temps cubique		${\displaystyle O(n^{3}) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>n</mi><mrow><mn>3</mn></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(n^{3})}</annotation></semantics></math></span><img src=$	${\displaystyle n^{3 <semantics><mrow><mstyle><msup><mi>n</mi><mrow><mn>3</mn></mrow></msup></mstyle></mrow><annotation>{\displaystyle n^{3}}</annotation></semantics></math></span><img src=$	Multiplication naïve de deux matrices. Calcul de la corrélation partielle . ${\displaystyle n imes n <semantics><mrow><mstyle><mi>n</mi><mo>×</mo><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n imes n}</annotation></semantics></math></span><img src=$
temps polynomial	P	${\displaystyle 2^{O(\log n)}={ extsf {poly}}(n) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mi>O</mi><mo>(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mrow></msup><mo>=</mo><mrow><mrow><mtext>poly</mtext></mrow></mrow><mo>(</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle 2^{O(\log n)}={ extsf {poly}}(n)}</annotation></semantics></math></span><img src=$	${\displaystyle n^{2}+n <semantics><mrow><mstyle><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>+</mo><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n^{2}+n}</annotation></semantics></math></span><img src=$ ${\displaystyle n^{10 <semantics><mrow><mstyle><msup><mi>n</mi><mrow><mn>10</mn></mrow></msup></mstyle></mrow><annotation>{\displaystyle n^{10}}</annotation></semantics></math></span><img src=$	Algorithme de Karmarkar pour la programmation linéaire . Test de primalité AKS
temps quasi-polynomial	QP	${\displaystyle 2^{{ extsf {poly}}(\log n) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mrow><mrow><mtext>poly</mtext></mrow></mrow><mo>(</mo><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{{ extsf {poly}}(\log n)}}</annotation></semantics></math></span><img src=$	${\displaystyle n^{\log \log n <semantics><mrow><mstyle><msup><mi>n</mi><mrow><mi>log</mi><mo>⁡</mo><mi>log</mi><mo>⁡</mo><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle n^{\log \log n}}</annotation></semantics></math></span><img src=$ ${\displaystyle n^{\log n <semantics><mrow><mstyle><msup><mi>n</mi><mrow><mi>log</mi><mo>⁡</mo><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle n^{\log n}}</annotation></semantics></math></span><img src=$	Meilleur algorithme d'approximation en O ( log₂n ⁾connu pour le problème de l'arbre de Steiner orienté , meilleur solveur de jeu de parité connu , meilleur algorithme d'isomorphisme de graphes connu
temps sous-exponentiel (première définition)	SUBEXP	${\displaystyle O(2^{n^{\epsilon }}) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mn>2</mn><mrow><msup><mi>n</mi><mrow><mi>ϵ</mi></mrow></msup></mrow></msup><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(2^{n^{\epsilon }})}</annotation></semantics></math></span><img src=$ $0 ϵ > 0$ 0		Contient BPP sauf si EXPTIME (voir ci-dessous) est égal à MA .
temps sous-exponentiel (deuxième définition)		${\displaystyle 2^{o(n) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mi>o</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{o(n)}}</annotation></semantics></math></span><img src=$	${\displaystyle 2^{\sqrt[{3}]{n <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mroot><mi>n</mi><mrow><mn>3</mn></mrow></mroot></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{\sqrt[{3}]{n}}}</annotation></semantics></math></span><img src=$	Meilleur algorithme classique pour la factorisation des entiers ancien meilleur algorithme pour l'isomorphisme de graphes
temps exponentiel (avec exposant linéaire)	E	${\displaystyle 2^{O(n) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{O(n)}}</annotation></semantics></math></span><img src=$	${\displaystyle 1.1^{n <semantics><mrow><mstyle><msup><mn>1.1</mn><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle 1.1^{n}}</annotation></semantics></math></span><img src=$ ${\displaystyle 10^{n <semantics><mrow><mstyle><msup><mn>10</mn><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle 10^{n}}</annotation></semantics></math></span><img src=$	Résolution du problème du voyageur de commerce par programmation dynamique
temps factoriel		${\displaystyle O(n)!=2^{O(n\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo><mo>!</mo><mo>=</mo><msup><mn>2</mn><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle O(n)!=2^{O(n\log n)}}</annotation></semantics></math></span><img src=$	${\displaystyle n!,n^{n},2^{n\log n <semantics><mrow><mstyle><mi>n</mi><mo>!</mo><mo>,</mo><msup><mi>n</mi><mrow><mi>n</mi></mrow></msup><mo>,</mo><msup><mn>2</mn><mrow><mi>n</mi><mi>log</mi><mo>⁡</mo><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle n!,n^{n},2^{n\log n}}</annotation></semantics></math></span><img src=$	Résolution du problème du voyageur de commerce par recherche exhaustive
temps exponentiel	EXPTIME	${\displaystyle 2^{{ extsf {poly}}(n) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mrow><mrow><mtext>poly</mtext></mrow></mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{{ extsf {poly}}(n)}}</annotation></semantics></math></span><img src=$	${\displaystyle 2^{n <semantics><mrow><mstyle><msup><mn>2</mn><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{n}}</annotation></semantics></math></span><img src=$ ${\displaystyle 2^{n^{2 <semantics><mrow><mstyle><msup><mn>2</mn><mrow><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{n^{2}}}</annotation></semantics></math></span><img src=$	Résolution de la multiplication de chaînes matricielles par recherche exhaustive . Recherche d'une stratégie gagnante aux échecs , aux dames ou au go avec la règle japonaise du ko sur un échiquier. ${\displaystyle n imes n <semantics><mrow><mstyle><mi>n</mi><mo>×</mo><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n imes n}</annotation></semantics></math></span><img src=$
temps double exponentiel	2-EXPTIME	${\displaystyle 2^{2^{{ extsf {poly}}(n) <semantics><mrow><mstyle><msup><mn>2</mn><mrow><msup><mn>2</mn><mrow><mrow><mrow><mtext>poly</mtext></mrow></mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow></msup></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{2^{{ extsf {poly}}(n)}}}</annotation></semantics></math></span><img src=$	${\displaystyle 2^{2^{n <semantics><mrow><mstyle><msup><mn>2</mn><mrow><msup><mn>2</mn><mrow><mi>n</mi></mrow></msup></mrow></msup></mstyle></mrow><annotation>{\displaystyle 2^{2^{n}}}</annotation></semantics></math></span><img src=$	Déterminer la vérité d'un énoncé donné en arithmétique de Presburger