Complexité d'un algorithme

La ressource la plus souvent prise en compte pour le calcul de la complexité est le temps. Lorsque le terme « complexité » est employé sans plus de précision, il désigne généralement la complexité temporelle.

Les unités de temps usuelles (secondes, minutes, etc.) ne sont pas utilisées en théorie de la complexité car elles dépendent trop de choix extérieurs (tels que l'ordinateur et l'évolution technologique). Il est interessant de noter qu'un ordinateur actuel peut exécuter un algorithme bien plus rapidement qu'un ordinateur des années 1960 ; toutefois, il ne s'agit pas d'une caractéristique intrinsèque de l'algorithme, mais plutôt d'une conséquence des progrès technologiques réalisés dans le domaine du matériel informatique. La théorie de la complexité cherche à quantifier les exigences temporelles intrinsèques aux algorithmes, c'est-à-dire les contraintes temporelles fondamentales qu'un algorithme impose à n'importe quel ordinateur. On y parvient en comptant le nombre d' opérations élémentaires exécutées lors du calcul. Ces opérations sont supposées s'effectuer en temps constant (c'est-à-dire indépendamment de la taille des données d'entrée) sur une machine donnée, ces opérations sont aussi appelées étapes.

Formellement, la complexité binaire désigne le nombre d'opérations sur les bits nécessaires au déroulement d'un algorithme. Dans la plupart des modèles de calcul, elle est égale à la complexité temporelle à une constante multiplicative près. Sur les ordinateurs, le nombre d'opérations sur les mots machine nécessaires est également proportionnel à la complexité binaire. Ainsi, la complexité temporelle et la complexité binaire sont équivalentes pour les modèles de calcul réalistes.

Une autre ressource importante est la quantité de mémoire nécessaire à l'exécution des algorithmes.

Pour les algorithmes basé sur le calcul distribué, généralement exécutés par plusieurs parties interagissant entre elles, la ressource la plus pertinente est la complexité de communication, c'est-à-dire la quantité nécessaire de communication entre ces parties.

Le nombre d'opérations arithmétiques réalisées est une autre mesure de la complexité couramment utilisée. On parle alors de complexité arithmétique . Si l'on connaît une limite supérieure à la taille de la représentation binaire des entrées dans un calcul, la complexité temporelle est équivalente à la complexité arithmétique à un facteur multiplicatif constant près.

Pour de nombreux algorithmes, la taille des entiers utilisés lors d'un calcul n'est pas bornée, et il n'est pas réaliste de considérer que les opérations arithmétiques s'effectuent en temps constant. Par conséquent, la complexité temporelle, généralement appelée complexité binaire dans ce contexte, peut être bien supérieure à la complexité arithmétique. Par exemple, la complexité arithmétique du calcul du déterminant d'une matrice à coefficients entiers n×n est de ${\displaystyle O(n^{3})}$ pour les algorithmes usuels ( pivot de Gauss ), la complexité binaire est exponentielle en n, car la taille des coefficients peut croître exponentiellement au cours du calcul. En revanche, si ces algorithmes sont associés à une arithmétique multimodulaire, la complexité binaire peut être réduite à O^~(n⁴) .

Par exemple pour les algorithmes de tri ou de recherche, la ressource généralement prise en compte est le nombre de comparaisons effectuées sur les entrées. Ce nombre constitue généralement une bonne mesure de la complexité temporelle si les données sont correctement organisées.

Il est impossible de dénombrer les étapes d'un algorithme pour toutes les entrées possibles. La complexité augmentant majoritairement avec la taille de l'entrée, elle est généralement exprimée en fonction de la taille n (en bits) de l'entrée. Cependant, la complexité d'un algorithme peut varier considérablement pour des entrées de même taille. C'est pourquoi plusieurs fonctions de complexité sont couramment utilisées.

La complexité dans le pire des cas correspond à la complexité maximale des calculs sur les entrées de taille n, tandis que la complexité moyenne correspond à la moyenne de ces dernières (elle est bien définie, puisque le nombre d'entrées possibles pour une taille fixée est fini). Conventionnellement, lorsque le terme « complexité » est utilisé sans autre précision, c'est la complexité temporelle dans le pire des cas qui est donnée.

Il est généralement difficile de calculer précisément les complexités ci-dessus. De plus, les valeurs exactes ont peu d'applications pratiques, car tout changement d'ordinateur ou de modèle de calcul affecterait potentiellement la complexité. Par ailleurs, l'utilisation des ressources n'est pas critique pour les entrées de petites taille, ce qui fait que, pour ces petites valeurs de n, la facilité d'implémentation est généralement plus importante qu'une faible complexité.

Pour ces raisons, on s'intéresse généralement au comportement de la complexité pour des valeurs de n significatives, c'est-à-dire à son comportement asymptotique (en) lorsque n tend vers l'infini. C'est pourquoi, la complexité est généralement exprimée à l'aide de la notation grand O.

Par exemple, l'algorithme usuel de multiplication des entiers a une complexité de ${\displaystyle O(n^{2}),}$ Cela signifie qu'il existe une constante ${\displaystyle c_{u}}$ tel que la multiplication de deux entiers d'au plus n chiffres puisse être effectuée en un temps inférieur à ${\displaystyle c_{u}n^{2}.}$ Cette borne est précise en ce sens que la complexité dans le pire des cas et la complexité dans le cas moyen sont ${\displaystyle \Omega (n^{2}),}$ ce qui signifie qu'il existe une constante ${\displaystyle c_{l}}$ de sorte que ces complexités sont plus grandes que ${\displaystyle c_{l}n^{2}.}$ La base n'apparaît pas dans cette complexité, car changer de base ne modifie que les constantes. ${\displaystyle c_{u}}$ et ${\displaystyle c_{l}.}$

L'évaluation de la complexité repose sur le choix d'un modèle de calcul, qui consiste à définir les opérations de base effectuées par unité de temps. Lorsque le modèle de calcul n'est pas explicitement spécifié, on suppose généralement implicitement qu'il s'agit d'une machine de Turing (ici à plusieurs bandes), car plusieurs modèles de calcul plus réalistes, tels que les Random-access machines, sont asymptotiquement équivalents pour la plupart des problèmes. Ce n'est que pour des problèmes très spécifiques et difficiles, comme la multiplication d'entiers en ${\displaystyle O(n\log n),}$ que cette équivalence est explicitement utilisée.

Un modèle de calcul déterministe est un modèle dans lequel le prochain état de la machine ainsi que les opérations à effectuer sont entièrement déterminés par l'état précédent. Historiquement, les premiers modèles déterministes furent les fonctions récursives, le lambda-calcul et les machines de Turing. Le modèle des machines à accès aléatoire (également appelées machines RAM) est aussi largement utilisé, car il représente une approximation plus fidèle des ordinateurs réels.

Lorsque le modèle de calcul n'est pas spécifié, on suppose généralement qu'il s'agit d'une machine de Turing à plusieurs bandes. Pour la plupart des algorithmes, la complexité temporelle est identique sur les machines de Turing à plusieurs bandes et sur les machines à mémoire vive, bien qu'il puisse être nécessaire d'optimiser le stockage des données en mémoire pour obtenir cette équivalence.

Par opposition au cas déterministe dans un modèle de calcul non déterministe, comme celui des machines de Turing non déterministes, des choix peuvent être effectués à certaines étapes du calcul. En théorie de la complexité, on considère simultanément tous les choix possibles, et la complexité temporelle non déterministe correspond au temps nécessaire pour que les meilleurs choix soient toujours effectués. Autrement dit, on considère que le calcul est effectué simultanément sur autant de processeurs (identiques) que nécessaire, et le temps de calcul non déterministe est le temps passé par le premier processeur à terminer le calcul. Ce parallélisme est partiellement compatible avec l'informatique quantique via la superposition d'états intriqués lors de l'exécution d'algorithmes quantiques spécifiques, comme par exemple la factorisation de Shor pour les petits entiers ( as of March 2018 : 21 = 3 × 7).

Même si un tel modèle de calcul n'est pas encore réaliste, il revêt une importance théorique, principalement liée au problème P = NP, qui remet en question l'identité des classes de complexité formées en prenant le « temps polynomial » et le « temps polynomial non déterministe » comme bornes supérieures. La simulation d'un algorithme NP sur un ordinateur déterministe prend généralement un « temps exponentiel ». Un problème appartient à la classe de complexité NP s'il peut être résolu en temps polynomial sur une machine non déterministe. Un problème est NP-complet si, on peut effectuer une réduction polynomiale vers ce problème depuis tous les autres de la classe (il est plus "sdifficile" que tous les autres). De nombreux problèmes combinatoires, tels que le problème du sac à dos, le problème du voyageur de commerce et le problème de la satisfaisabilité booléenne, sont NP-complets. Pour tous ces problèmes, le meilleur algorithme connu a une complexité exponentielle. Si l'un de ces problèmes pouvait être résolu en temps polynomial sur une machine déterministe, alors tous les problèmes NP pourraient également être résolus en temps polynomial, et l'on aurait P = NP. On conjecture généralement que P ≠ NP, ce qui implique concrètement que les pires cas de problèmes NP sont intrinsèquement difficiles à résoudre, c'est-à-dire qu'ils prennent plus de temps que toute période raisonnable (des décennies !) pour des longueurs d'entrée intéressantes.

Les calcul parallèles et distribués consistent à répartir les calculs sur plusieurs processeurs fonctionnant simultanément. La différence entre ces deux modèles repose principalement sur le mode de transmission des informations entre les processeurs. En calcul parallèle, la transmission des données est généralement très rapide, tandis qu'en calcul distribué, elle s'effectue via un réseau et est donc beaucoup plus lente.

Le temps nécessaire à un calcul sur N processeurs est au moins égal au quotient par N du temps nécessaire à un seul processeur pour résoudre le même problème. En réalité, cette limite théoriquement optimale ne peut jamais être atteinte, car certaines sous-tâches ne peuvent être parallélisées et certains processeurs peuvent devoir attendre le résultat d'un autre processeur.

Le principal problème de complexité réside donc dans la conception d'algorithmes tels que le produit du temps de calcul par le nombre de processeurs soit aussi proche que possible du temps nécessaire au même calcul sur un seul processeur.

Un ordinateur quantique est un ordinateur dont le modèle de calcul repose sur la mécanique quantique. La thèse de Church-Turing s'applique aux ordinateurs quantiques : tout problème résoluble par un ordinateur quantique l'est également par une machine de Turing. Cependant, certains problèmes pourraient théoriquement être résolus avec une complexité temporelle bien moindre grâce à l'aide des phénomènes quantiques qu'avec les technologies aujourd'hui utilisées.

La principale différence entre les circuits actuels et les circuits quantique est la continuité de l'ensemble des états possibles. La défis de construction de tels ordinateurs se situe dans la précision des portes logiques quantiques et dans la préservation des bits quantiques (qubits). Le nombre de portes logiques quantiques est infini, mais il est théoriquement possible de réaliser une ${\displaystyle (1-\epsilon )}$-approximation avec un ensemble fini de portes^[2].

Dans le contexte de la résolution de problème et par conséquent des algorithmes, on a créé différentes classes de complexité spécifiques aux algorithmes quantiques. La plus petite concerne les algorithmes approchés sur des problèmes d'optimisation (l'approximation standard étant ${\displaystyle 2/3}$). Cette classe est nommée ${\displaystyle BQP}$ (bounded error quantum polynomial time) reprend le principe de son homologue ${\displaystyle BPP}$ (bounded-error probabilistic polynomial time) mais pour les ordinateurs quantiques.

On peut émuler un algorithme sur machine de Turing par un algorithme quantique en temps polynomial donc ${\displaystyle BPP\subset BQP}$. De plus les différentes propriétés quantiques des qbits telles que la superposition permettent de simuler efficacement (polynomialement) certaines classes de problèmes. Par exemple les problèmes se réduisant de la factorisation ont une résolution polynomiale pour les ordinateurs quantiques (par l'algorithme de Shor).

La théorie de la complexité quantique (en) a été développée pour étudier les classes de complexité des problèmes solubles par les ordinateurs quantiques. Elle est utilisée en cryptographie post-quantique, qui consiste à concevoir des protocoles cryptographiques résistants théoriquement aux attaques des ordinateurs quantiques.

La complexité d'un problème est l'infimum des complexités des algorithmes susceptibles de résoudre ce problème, y compris les algorithmes inconnus. La complexité d'un problème n'est donc pas supérieure en complexité à tout algorithme permettant de le résoudre.

Il vient que toute complexité d'un algorithme, exprimée avec la notation grand O, est par conséquent une borne supérieure de la complexité du problème correspondant.

En revanche, il est généralement difficile d'obtenir des bornes inférieures non triviales pour la complexité du problème, et il existe peu de méthodes pour en obtenir.

Pour résoudre la majorité des problèmes, il est nécessaire de lire toutes les données d'entrée, ce qui prend généralement un temps proportionnel à leur taille des. Ainsi, ces problèmes ont une complexité au moins linéaire, c'est-à-dire, en utilisant la notation grand oméga, une complexité en ${\displaystyle \Omega (n).}$

La résolution de certains problèmes, notamment en calcul formel et en géométrie algébrique algorithmique, peut être très volumineuse. Dans ce cas, la complexité est minorée par la taille maximale de la sortie, puisque celle-ci doit être écrite. Par exemple, un système de n équations polynomiales de degré d à n indéterminées peut avoir jusqu'à… ${\displaystyle d^{n}}$ Il existe des solutions complexes si leur nombre est fini (c'est le théorème de Bézout ). Comme ces solutions doivent être écrites, la complexité de ce problème est O(n²). ${\displaystyle \Omega (d^{n}).}$ Pour ce problème, un algorithme de complexité ${\displaystyle d^{O(n)}}$ est connu, ce qui peut donc être considéré comme asymptotiquement quasi-optimal.

Une borne inférieure non linéaire de ${\displaystyle \Omega (n\log n)}$ La complexité est connue pour correspondre au nombre de comparaisons nécessaires à un algorithme de tri. Ainsi, les meilleurs algorithmes de tri sont optimaux, car leur complexité est ${\displaystyle O(n\log n).}$ Cette borne inférieure résulte du fait qu'il existe n! façons d'ordonner n objets. Comme chaque comparaison divise cet ensemble de n! ordres en deux parties, le nombre N de comparaisons nécessaires pour distinguer tous les ordres doit être vérifié. ${\displaystyle 2^{N}>n!,}$ ce qui implique ${\displaystyle N=\Omega (n\log n),}$ selon la formule de Stirling.

Une méthode standard pour obtenir des bornes inférieures de complexité consiste à réduire un problème à un autre. Plus précisément, supposons qu'il soit possible d'encoder un problème A de taille n en un sous-problème de taille f(n) d'un problème B, et que la complexité de A soit ${\displaystyle \Omega (g(n)).}$ Sans perte de généralité, on peut supposer que la fonction f croît avec n et possède une fonction inverse h . Alors la complexité du problème B est ${\displaystyle \Omega (g(h(n))).}$ C'est la méthode utilisée pour prouver que, si P ≠ NP (une conjecture non résolue), la complexité de tout problème NP-complet est ${\displaystyle \Omega (n^{k}),}$ pour tout entier positif k .