Complexité temporelle

Graphiques de fonctions couramment utilisées dans l' analyse des algorithmes , montrant le nombre d'opérations N en fonction de la taille n des données d'entrée pour chaque fonction.

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 la 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 d'une 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. etc., où $bits nécessaire pour représenter l'entrée.$

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 dont la complexité temporelle est O(n) = 1/n. $0 α > 0$

NomClasse de complexitéComplexité temporelle 10Trouver la valeur médiane dans un tableau trié de nombres. Calculer

0 ϵ > 0

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.$

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 en utilisant une variante de recherche binaire). Une notion étroitement liée est celle des temps, si sa complexité temporelle est En termes simples, cela signifie que 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 pour chaque entrée de taille 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 (également appelé temps log-linéaire ) si $0 ε > 0$

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

Tri fusion sur place ,
Tri rapide , $, dans sa version aléatoire, a un temps d'exécution qui est en prévision du pire scénario. Sa version non randomisée possède un temps d'exécution uniquement en considérant la complexité moyenne des cas.$
Tri par tas , $, tri fusion, tri intro, tri par arbre binaire, tri lissé, tri patient, etc. dans le pire des cas$
Transformées de Fourier rapides ,
calcul de tableau de Monge ,
Algorithme de Schönhage – Strassen pour la multiplication ,

Dans de nombreux cas, le $Le temps d'exécution est simplement le résultat de l'exécution d'une L'opération est répétée le tri par arbre binaire crée un arbre binaire en insérant chaque élément du tableau de taille arbre binaire de recherche auto-équilibré prend O (n²). En temps, l'algorithme complet prend du temps. temps.$

Les tris par comparaison nécessitent au moins $comparaisons dans le pire des cas parce que, par approximation de Stirling . Elles résultent aussi fréquemment de la relation de récurrence. .$

Temps sous-quadratique

Un algorithme est dit avoir un temps sous-quadratique si $.$

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

majoré par une expression polynomiale en fonction de la taille de son entrée, c'est-à-dire Les problèmes pour lesquels il existe un algorithme déterministe polynomial appartiennent à la classe de complexité P théorie de la complexité algorithmique . La thèse de Cobham affirme que le temps polynomial est synonyme de « traitable », « faisable », « efficace » ou « rapide ».

Quelques exemples d'algorithmes en temps polynomial :

L' algorithme de tri par sélection sur n entiers effectue $opérations pour une certaine constante A. Ainsi, il s'exécute en temps et est un algorithme à durée polynomiale.$
Toutes les opérations arithmétiques de base (addition, soustraction, multiplication, division et comparaison) peuvent être effectuées en temps polynomial.
On peut trouver les couplages maximaux dans les graphes en temps polynomial. Dans certains contextes, notamment en optimisation , on distingue les algorithmes à complexité polynomiale forte et les algorithmes à complexité polynomiale faible .

Ces deux concepts ne sont pertinents que si les entrées des algorithmes sont des entiers.

Classes de complexité

Le concept de temps polynomial donne lieu à plusieurs classes de complexité en théorie de la complexité algorithmique. Voici quelques classes importantes définies à l'aide du temps polynomial.

P : La classe de complexité des problèmes de décision qui peuvent être résolus sur une machine de Turing déterministe en temps polynomial
NP : La classe de complexité des problèmes de décision qui peuvent être résolus sur une machine de Turing non déterministe en temps polynomial
ZPP : La classe de complexité des problèmes de décision qui peuvent être résolus sans erreur sur une machine de Turing probabiliste en temps polynomial
RP : La classe de complexité des problèmes de décision qui peuvent être résolus avec une erreur unilatérale sur une machine de Turing probabiliste en temps polynomial.
BPP : Classe de complexité des problèmes de décision pouvant être résolus avec une erreur bilatérale sur une machine de Turing probabiliste en temps polynomial
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 ayant un temps superpolynomial si T ( n ) n'est majoré par aucun polynôme ; c'est-à-dire si tout entier positif $test de primalité d'Adleman-Pomerance-Rumely s'exécute en un temps 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

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 de

pour certains fixes 0 .

Quand

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 0"}},"i":0}}] 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)"

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 des temps d'exécution dans $[ temps sous-exponentiel est l'algorithme classique le plus connu pour la factorisation d'entiers, le crible général des corps de nombres, qui s'exécute en un temps d'environ O(n²). où la longueur de l'entrée est problème d'isomorphisme de graphes , que le meilleur algorithme connu de 1982 à 2016 a résolu en . Cependant, lors de STOC 2016, un algorithme en temps quasi-polynomial a été présenté.$

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 par la considération de paires. $des problèmes de décision et des paramètres k . SUBEPT est la classe de tous les problèmes paramétrés qui s'exécutent en temps sous-exponentiel en k et polynomial en taille d'entrée n :$

Plus précisément, SUBEPT est la classe de tous les problèmes paramétrés $pour laquelle il existe une fonction calculable avec et un algorithme qui décide L dans le temps .$

Hypothèse du temps exponentiel

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 0"}},"i":0}}] 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

P \neq 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 .

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 .

Temps factoriel

Un algorithme est dit à temps factoriel si T(n) est majoré par la fonction factorielle n!. Le temps factoriel est un sous-ensemble du temps exponentiel (EXP) car $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 .

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.