Utilisateur:Argos42/draft2

Généralités

Introduction

Un problème informatique est résolu par un algorithme, ce dernier est composé d'un ensemble d'étapes simples qui permettent d'obtenir un résultat au problème donné. Souvent, le nombre d'étapes nécessaires à la résolution varie en fonction du nombre d'éléments à traiter. Pour un même problème, plusieurs algorithmes peuvent aussi exister. La complexité d'un algorithme représente le nombre d'étapes qui seront nécessaires pour traiter un problème donné pour une entrée de taille donnée.

Exemple

Supposons que le problème posé soit de trouver un nom dans un annuaire téléphonique. Il existe plusieurs méthodes pour rechercher le nom :

1. Parcourir les pages dans l'ordre jusqu'à trouver le nom
2. Ouvrir l'annuaire au milieu, si le nom est plus petit, regarder avant, sinon, regarder après. Refaire la même opération jusqu'à trouver le nom.

Pour le problème donné, il existe deux méthodes. Pour chacune de ces méthodes il existe un pire cas et un meilleur cas. Prenons la méthode 1 :

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

Si l'annuaire contient 30000 noms, le pire des cas demandera plus d'étapes que si l'annuaire contient 3 noms. La complexité de cette première méthode est évaluée à $O(n)$: il faut parcourir tous les noms ($n$ noms) une fois dans le pire des cas pour $n$ entrées dans l'annuaire fourni.

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'une seule page. Le nombre d'étapes nécessaire sera $log_{2}n$. La complexité de ce second algortihme dans le pire des cas sera alors évaluée à $O(logn)$.

Complexité, comparatif

Pour donner un ordre d'idée sur les différentes complexité, 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 la-dite complexité. Les temps d'exécutions 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.

Notation	Type de complexité	Temps pour n=5	Temps pour n=10	Temps pour n=20	Temps pour n=50	Temps pour n=250	Temps pour n=1000	Temps pour n=10000	Temps pour n=1000000	Problème exemple
$O(1)$	complexité constante	10ns	10ns	10ns	10ns	10ns	10ns	10ns	10ns
$O(\log(n))$	complexité logarithmique	10ns	10ns	10ns	20ns	30ns	30ns	40ns	60ns
$O(n)$	complexité linéaire	50ns	100ns	200ns	500ns	2.5µs	10µs	100µs	10ms
$O(n\log(n))$	complexité quasi-linéaire	40ns	100ns	260ns	850ns	6µs	30µs	400µs	60ms
$O(n^{2})$	complexité quadratique (polynomiale)	250ns	1µs	4µs	25µs	625µs	10ms	1s	2.8heures
$O(n^{3})$	complexité cubique (polynomiale)	1.25µs	10µs	80ms	1.25ms	156ms	10s	2.7heures	316ans
$O(n^{\log(n)})$	complexité quasi-polynomiale	30ns	100ns	492ns	7µs	5ms	10s	3.2ans	$10^{20}$ans
$O(2^{n})$	complexité exponentielle	320ns	10µs	10ms	130jours	$10^{59}$ans	...	...	...
$O(n!)$	complexité factorielle	1.2µs	36ms	770ans	$10^{48}ans$	...	...	...

Présentation

La théorie de la complexité s'attache à connaître la difficulté (ou la complexité) d'une réponse par algorithme à un problème, dit algorithmique, posé de façon mathématique. Pour la définir, il faut présenter les concepts de problèmes algorithmiques, de réponses algorithmiques aux problèmes, et la complexité des problèmes algorithmiques.

Problème algorithmique

Un problème algorithmique est un problème posé de façon mathématique, c'est-à-dire qu'il est énoncé rigoureusement dans le langage des mathématiques – le mieux étant d'utiliser le calcul des prédicats. Il comprend des hypothèses, des données et une question. On distingue deux types de problèmes :

• les problèmes de décision : ils posent une question dont la réponse est oui ou non ;
• les problèmes d'existence ou de recherche d'une solution : ils comportent une question ou plutôt une injonction de la forme « trouver un élément tel que …» dont la réponse consiste à fournir un tel élément.

Réponse algorithmique

Dans chaque catégorie de problèmes ci-dessus, on dit qu'un problème a une réponse algorithmique si sa réponse peut être fournie par un algorithme. Un problème est décidable s'il s'agit d'un problème de décision – donc d'un problème dont la réponse est soit oui soit non – et si sa réponse peut être fournie par un algorithme. Symétriquement, un problème est calculable s'il s'agit d'un problème d'existence et si l'élément calculé peut être fourni par un algorithme. La théorie de la complexité ne couvre que les problèmes décidables ou calculables et cherche à évaluer les ressources – temps et espace mémoire – mobilisées pour obtenir algorithmiquement la réponse.

Complexité d'un problème algorithmique

La théorie de la complexité vise à savoir si la réponse à un problème peut être donnée très efficacement, efficacement ou au contraire être inatteignable en pratique (et en théorie), avec des niveaux intermédiaires de difficulté entre les deux extrêmes ; pour cela, elle se fonde sur une estimation – théorique – des temps de calcul et des besoins en mémoire informatique. Dans le but de mieux comprendre comment les problèmes se placent les uns par rapport aux autres, la théorie de la complexité établit des hiérarchies de difficultés entre les problèmes algorithmiques, dont les niveaux sont appelés des « classes de complexité ». Ces hiérarchies comportent des ramifications, suivant que l'on considère des calculs déterministes – l'état suivant du calcul est « déterminé » par l'état courant – ou non déterministes.

De l'existence à la décision

Un problème d'existence peut être transformé en un problème de décision équivalent. Par exemple, le problème du voyageur de commerce qui cherche, dans un graphe dont les arêtes sont étiquetées par des coûts, à trouver un cycle, de coût minimum, passant une fois par chaque sommet, peut s'énoncer en un problème de décision comme suit : Existe-t-il un cycle passant une fois par chaque sommet tel que tout autre cycle passant par tous les sommets ait un coût supérieur. L'équivalence de ces deux problèmes suppose que la démonstration d'existence repose sur un argument constructif, c'est-à-dire, par exemple dans le cas du voyageur de commerce, fournit effectivement un cycle de coût minimum dans le cas où on a montré qu'un cycle de coût minimum existe. Le problème de l'existence d'un cycle de coût minimum est équivalent au problème du voyageur de commerce, au sens où si l'on sait résoudre efficacement l'un, on sait aussi résoudre efficacement l'autre. Dans la suite de cet article, nous ne parlerons donc que de problème de décision.

Modèle de calcul

L'analyse de la complexité est étroitement associée à un modèle de calcul. L'un des modèles de calcul les plus utilisés est celui des machines abstraites dans la lignée du modèle proposé par Alan Turing en 1936.

Les deux modèles les plus utilisés en théorie de la complexité sont :

• La machine de Turing ;
• La machine RAM (Random Access Machine).

Dans ces deux modèles de calcul, un calcul est constitué d'étapes élémentaires ; à chacune de ces étapes, pour un état donné de la mémoire de la machine, une action élémentaire est choisie dans un ensemble d'actions possibles. Les machines déterministes sont telles que chaque action possible est unique, c'est-à-dire que l'action à effectuer est dictée de façon unique par l'état courant de celle-ci. S'il peut y avoir plusieurs choix possibles d'actions à effectuer, la machine est dite non déterministe. Il peut sembler naturel de penser que les machines de Turing non déterministes sont plus puissantes que les machines de Turing déterministes, autrement dit qu'elles peuvent résoudre en un temps donné des problèmes que les machines déterministes ne savent pas résoudre dans le même temps.

D'autres modèles de calcul qui permettent d'étudier la complexité s'appuient sur :

• les fonctions récursives dues à Kleene ;
• le lambda-calcul ;
• les automates cellulaires ;
• la logique linéaire.

Complexité en temps et en espace

Sans nuire à la généralité on peut supposer que les problèmes que nous considérons n'ont qu'une donnée. Cette donnée a une taille qui est un nombre entier naturel. La façon dont cette taille est mesurée joue un rôle crucial dans l'évaluation de la complexité de l'algorithme. Ainsi si la donnée est elle-même un nombre entier naturel, sa taille peut être appréciée de plusieurs façons : on peut dire que la taille de l'entier p vaut p, mais on peut aussi dire qu'elle vaut log(p) parce que l'entier a été représenté en numération binaire ou décimale ce qui raccourcit la représentation des nombres, ainsi 1 024 peut être représenté avec seulement onze chiffres binaires et quatre chiffres décimaux et donc sa taille est 11 ou 4 et non pas de l'ordre de 1 000. Le but de la complexité est de donner une évaluation du temps de calcul ou de l'espace de calcul nécessaire en fonction de cette taille, qui sera notée n. L'évaluation des ressources requises permet de répartir les problèmes dans des classes de complexité.

Pour les machines déterministes, on définit la classe TIME(t(n)) des problèmes qui peuvent être résolus en temps t(n). C'est-à-dire pour lesquels il existe au moins un algorithme sur une machine déterministe résolvant le problème en temps t(n). Le temps est le nombre de transitions sur machine de Turing ou le nombre d’opérations sur machine RAM, mais en fait ce temps n'est pas une fonction précise, mais c'est un ordre de grandeur, on parle aussi d'évaluation asymptotique, ainsi pour un temps qui s'évalue par un polynôme ce qui compte c'est le degré du polynôme, si ce degré est 2, on dira que l'ordre de grandeur est en O(n²), que la complexité est quadratique et que le problème appartient à la classe TIME(n²).

Notation	Type de complexité
$O(1)$	complexité constante (indépendante de la taille de la donnée)
$O(\log(n))$	complexité logarithmique
$O(n)$	complexité linéaire
$O(n\log(n))$	complexité quasi-linéaire
$O(n^{2})$	complexité quadratique
$O(n^{3})$	complexité cubique
$O(n^{p})$	complexité polynomiale
$O(n^{\log(n)})$	complexité quasi-polynomiale
$O(2^{n})$	complexité exponentielle
$O(n!)$	complexité factorielle

Les quatre familles de classes de complexité en temps et en espace

Suivant qu'il s'agit de temps et d'espace, de machine déterministes ou non déterministes, on distingue quatre classes de complexité.

• TIME(t(n)) est la classe des problèmes de décision qui peuvent être résolus en temps de l'ordre de grandeur de t(n) sur une machine déterministe.
• NTIME(t(n)) est la classe des problèmes de décision qui peuvent être résolus en temps de l'ordre de grandeur de t(n) sur une machine non déterministe.
• SPACE(s(n)) est la classe des problèmes de décision qui requièrent pour être résolus un espace de l'ordre de grandeur de s(n) sur une machine déterministe.

• NSPACE(s(n)) est la classe des problèmes de décision qui requièrent pour être résolus un espace de l'ordre de grandeur de s(n) sur une machine non déterministe.