complexité d'un algorithme

Imaginez un programme qui cherche le plus petit nombre d'une liste. Avec 8 nombres, il compare le minimum provisoire aux 7 autres. Avec une liste beaucoup plus longue, le nombre de comparaisons augmente presque comme sa longueur.

La complexité décrit cette croissance, plutôt que la durée mesurée sur un ordinateur particulier. Elle peut suivre le travail effectué, la mémoire supplémentaire utilisée ou, plus rarement, la taille du programme.

La complexité d'un algorithme mesure l'ordre de grandeur des ressources consommées en fonction de la taille de l'entrée. On note cette taille n. La ressource étudiée doit être précisée : la complexité temporelle compte des opérations élémentaires, tandis que la complexité spatiale évalue la mémoire mobilisée. La longueur de description mesure, dans d'autres contextes, la taille du programme lui-même.

La notation grand O exprime une borne asymptotique. Pour deux fonctions positives T et g, écrire $T(n)\in O(g(n))T(n)\; \backslash in\; O(g(n))$ signifie qu'il existe une constante positive c et un rang n₀ tels que, pour tout n au moins égal à n₀, le coût T(n) ne dépasse pas c fois g(n). Cette notation décrit la croissance pour les grandes entrées ; elle ne donne ni le temps exact ni une unité universelle.

Deux algorithmes qui résolvent le même problème peuvent ainsi être comparés dans un même modèle de calcul. Il faut aussi annoncer le cas étudié, par exemple le pire cas, le meilleur cas ou le coût moyen selon une distribution d'entrées précisée.

Pour analyser un algorithme, choisissez d'abord une taille d'entrée n et une ressource mesurable. Comptez ensuite le coût T(n) dans un cas annoncé, puis conservez un ordre de grandeur qui le borne à partir d'un certain rang.

Le critère s'écrit : $T(n)\le cg(n)\text{pour tout }n\ge n_{0}T(n)\; \backslash le\; c\backslash ,g(n)\; \backslash quad\; \backslash text\{pour\; tout\; \}\; n\; \backslash ge\; n\_0$, avec c strictement positif. On conclut alors que T appartient à O(g). Les constantes et les termes moins rapides peuvent être absorbés, mais le cas analysé et la ressource comptée restent indispensables.

L'analyse s'applique à un algorithme défini, à une mesure de taille et à un modèle de calcul. Il faut pouvoir vérifier trois choix : ce que n compte, quelle opération ou quelle mémoire constitue le coût, et si l'on étudie le pire cas, le meilleur cas ou une moyenne fondée sur une distribution.

Si deux programmes sont chronométrés sur des machines différentes, leurs durées brutes ne suffisent pas à comparer leur complexité. Il faut revenir à un même modèle de coût, ou mener un benchmark contrôlé si la question porte sur les performances réelles.

On cherche le minimum de la liste 12, 5, 9, 3, 8, 6, 11, 4. La taille de l'entrée est n = 8. L'opération comptée est la comparaison entre le minimum provisoire et le nombre suivant.

1. On prend 12 comme minimum provisoire.
2. On le compare successivement à 5, 9, 3, 8, 6, 11 puis 4.
3. Le minimum provisoire devient 5, puis 3, et reste 3 jusqu'à la fin.

Après le premier nombre, chacun des n − 1 nombres restants provoque exactement une comparaison. Le coût est donc $T(n)=n-1T(n)=n-1$, ce qui appartient à O(n). La figure représente ces comptes exacts pour des listes de 1 à 8 nombres.

Pour n = 8, on obtient 7 comparaisons et le résultat 3. Le contrôle consiste à recompter les sept nombres examinés après 12. Si seul le minimum provisoire est stocké en plus de la liste, la mémoire auxiliaire reste constante : elle appartient à O(1).

Pour choisir entre deux algorithmes qui donnent le même résultat, on compare leur croissance sur la taille d'entrée attendue. Une meilleure classe asymptotique devient décisive lorsque les données peuvent devenir grandes ; pour de petites entrées, un test mesuré peut départager les constantes cachées.

Quand le temps de réponse est critique, on examine la complexité temporelle dans le cas pertinent. Quand la mémoire est limitée, on regarde aussi l'espace auxiliaire, car un algorithme rapide peut employer davantage de stockage.

Pour une implantation précise, l'analyse asymptotique sert de premier filtre. Le profilage ou le benchmark devient l'outil adapté si l'on doit ensuite mesurer l'effet du langage, du matériel, des entrées réelles et des constantes.

Complexité temporelle et temps d'exécution. La première décrit une croissance en fonction de n ; le second est une durée mesurée dans des conditions précises. Deux exécutions de 10 ms sur des machines différentes ne prouvent donc pas une même complexité.

Grand O et coût exact. T(n) = n − 1 donne le nombre exact de comparaisons dans l'exemple, tandis que O(n) n'en conserve qu'une borne de croissance. Pour n = 8, le premier donne 7 ; le second ne donne pas ce nombre.

Complexité spatiale et taille de l'entrée. Une convention peut compter toute la mémoire ou seulement l'espace auxiliaire. Dans la recherche du minimum, la liste occupe une place proportionnelle à n, mais le stockage supplémentaire peut rester constant.

Petites entrées. Une meilleure croissance asymptotique ne garantit pas le programme le plus rapide pour une taille donnée. Le symptôme est un benchmark contraire au classement théorique ; il faut alors mesurer les constantes et le seuil de croisement.

Cas non annoncé. Un même algorithme peut avoir des coûts différents au meilleur et au pire cas. Une valeur unique sans qualification est ambiguë ; il faut nommer le cas ou la distribution utilisée pour une moyenne.

Taille mal choisie. Une entrée peut avoir plusieurs dimensions, comme un graphe avec des sommets et des arêtes. Si un seul n masque cette structure, il faut exprimer le coût avec les paramètres qui gouvernent réellement les opérations.

Seuil n = 1. La recherche du minimum effectue alors zéro comparaison, car T(1) = 0. Ce cas ne contredit pas O(n) : la notation décrit une borne à partir d'un certain rang, pas chaque valeur isolée.

Algorithme. Revenir à la notion d'algorithme précise l'objet dont on compte les opérations et les ressources.

Grand O. Approfondir la notation clarifie ce qu'une borne asymptotique affirme, et ce qu'elle ne chiffre pas.

Algorithme de tri. Ce cas concret montre pourquoi plusieurs procédures résolvant le même problème doivent être comparées.