classe de complexité

Imaginez une liste non triée de dix nombres et demandez si elle contient 7. Une recherche peut devoir examiner les dix positions. Avec vingt nombres, elle peut en examiner vingt. Le temps nécessaire grandit ici au même rythme que la taille de la liste.

Une classe de complexité rassemble des problèmes selon la manière dont une ressource nécessaire augmente quand l'entrée grandit. La ressource peut être le temps de calcul ou la mémoire. Cette comparaison porte sur la croissance, et non sur la vitesse d'un ordinateur particulier.

Une classe de complexité est un ensemble de problèmes algorithmiques qui partagent une borne portant sur une ressource de calcul. Cette ressource est notamment le temps d'exécution ou l'espace mémoire. La taille de l'entrée est notée n. La borne décrit le comportement lorsque n devient grand, sans dépendre des détails d'implémentation ni des performances d'une machine donnée.

La notation grand O exprime une majoration asymptotique. Dire qu'un algorithme utilise un temps O(n) signifie qu'à partir d'une certaine taille, son nombre d'opérations est borné par une constante multipliée par n. De même, O(n²) décrit une borne quadratique. Les constantes et les petites tailles peuvent modifier le temps observé, mais pas la forme asymptotique de cette borne.

Un problème est polynomial s'il existe au moins un algorithme qui le résout avec un nombre d'opérations borné asymptotiquement par un polynôme en n. La classe P regroupe les problèmes résolus de cette façon par un algorithme déterministe. L'existence d'un tel algorithme suffit : un autre algorithme plus lent pour le même problème ne retire pas celui-ci de P.

On cherche si la valeur 7 figure dans une liste non triée. Les données sont une liste de taille n, une valeur cible et une réponse attendue de type oui ou non. Pour un premier contrôle, prenons n = 10.

1. On compare 7 au premier élément.
2. Si les valeurs diffèrent, on passe à l'élément suivant.
3. On s'arrête dès que 7 est trouvé, ou après le dernier élément.

Dans le pire cas, 7 est absent ou occupe la dernière position. Pour n = 10, la recherche effectue alors exactement 10 comparaisons. Pour n = 20, elle en effectue exactement 20.

Le nombre maximal de comparaisons est donc égal à n. Il est borné par le polynôme n, ce qui donne une complexité temporelle O(n). Ce problème de décision admet ainsi un algorithme déterministe polynomial et appartient à P.

Le contrôle est refaisable : doubler la longueur de 10 à 20 double le maximum de 10 à 20 comparaisons. La figure représente cette relation exacte pour toutes les tailles entières de 0 à 20.

Pour comparer deux méthodes qui résolvent le même problème, on regarde comment leur consommation de temps ou de mémoire évolue avec la taille de l'entrée. Une mesure chronométrée suffit pour une machine donnée ; une borne asymptotique est préférable lorsque l'on veut comparer leur croissance indépendamment du matériel.

Pour classer un problème, il faut chercher une garantie valable pour toutes les entrées de la taille considérée, et pas seulement un essai favorable. Dans la recherche séquentielle d'une valeur au sein de la liste non triée étudiée ici, le pire cas impose d'aller jusqu'au dernier élément : c'est ce maximum qui justifie la borne O(n).

Si la ressource étudiée change, la question change aussi. Une classe de temps compare le nombre d'étapes ; une classe d'espace compare la mémoire nécessaire. Il faut donc annoncer la ressource avant d'interpréter la classe.

Classe de complexité et complexité d'un algorithme. La complexité d'un algorithme borne les ressources consommées par une procédure précise. Une classe rassemble des problèmes satisfaisant un même critère. Ainsi, la recherche séquentielle a un temps O(n), tandis que le problème de décision « 7 est-il présent ? » appartient à P parce qu'un algorithme polynomial le résout.

Temps observé et complexité asymptotique. Un chronomètre mesure une durée sur une machine et une entrée particulières. Grand O décrit une borne de croissance quand n augmente. Deux programmes peuvent donc avoir la même borne O(n) et des durées mesurées différentes.

Une entrée favorable ne suffit pas. Si 7 est en première position, une seule comparaison suffit, même dans une très longue liste. Ce cas ne prouve pas une borne constante pour toutes les entrées. Il faut annoncer si l'on étudie le meilleur cas, le pire cas ou un autre cadre.

Grand O n'est pas une égalité exacte. Écrire O(n) n'affirme pas que chaque exécution effectue n opérations. Dans l'exemple, le maximum vaut exactement n comparaisons, mais une recherche peut s'arrêter avant. Il faut séparer le coût exact d'une entrée de sa borne asymptotique.

Un algorithme lent ne classe pas à lui seul le problème. On peut volontairement résoudre la recherche avec des opérations inutiles. Cela ne change pas l'appartenance à P, car un algorithme déterministe polynomial existe déjà. Il faut raisonner sur l'existence d'un algorithme satisfaisant la borne.

La taille n = 0 reste un cas valide. La liste vide ne demande aucune comparaison d'élément et la réponse est immédiatement non. Le modèle donne bien zéro comparaison ; il ne faut pas supposer que l'entrée contient au moins une valeur.

Une même idée de classement s'étend en changeant la ressource bornée ou la forme de la borne. On peut alors étudier séparément le temps et l'espace, puis demander comment les classes obtenues se comparent. La question essentielle reste la même : quelle garantie subsiste lorsque la taille de l'entrée devient grande ?