Complexité

« Peut-on faire mieux ? » Toute l’algorithmique tient peut-être dans cette question. Tim Roughgarden (auteur de la série de livres Algorithms Illuminated tirés de ses cours) en fait le mantra du concepteur d’algorithmes.

Mesurer sans chronomètre

Chronométrer un programme renseigne sur une machine, un langage, un jour donné. Pour comparer des algorithmes, on compte plutôt le nombre d’opérations élémentaires (comparaisons, additions, accès à une case…) en fonction de la taille $n$ de l’entrée, dans le pire des cas. Et l’on ne garde de ce décompte que son ordre de grandeur : $3n^2+10n+7$ opérations, c’est « du $n^2$ ».

La notation $\mathcal{O}$

Intuition. $f=\mathcal{O}(g)$ signifie que, pour $n$ assez grand, $f$ ne croît pas plus vite que $g$, à une constante multiplicative près.

Définition. Soient $f$ et $g$ deux suites à valeurs positives. On note $f(n)=\mathcal{O}(g(n))$ s’il existe une constante $c>0$ et un rang $n_0\in\mathbb{N}$ tels que

$$\forall n\geqslant n_0,\quad f(n)\leqslant c\,g(n).$$

Exemple. $3n^2+10n+7=\mathcal{O}(n^2)$ : avec $c=4$, il suffit que $n^2\geqslant 10n+7$, ce qui est vrai dès $n_0=11$.

On note de même $f=\Omega(g)$ quand $f$ est minorée par un multiple de $g$ à partir d’un certain rang, et $f=\Theta(g)$ quand on a les deux : $f$ et $g$ ont alors exactement le même ordre de grandeur.

Pourquoi oublier les constantes ?

Roughgarden donne trois raisons. Les constantes dépendent du langage, du compilateur et de la machine : elles ne disent rien de l’algorithme lui-même. Quand $n$ grandit, c’est la vitesse de croissance qui l’emporte, et de loin. Enfin, ce niveau de détail est un juste milieu : assez grossier pour s’affranchir de l’anecdotique, assez fin pour départager les algorithmes. Un algorithme « rapide » est simplement un algorithme dont le temps d’exécution, dans le pire des cas, croît lentement avec la taille de l’entrée.

Faites varier la taille de l’entrée ci-dessous : à $n=100$, un algorithme en $2^n$ demande déjà près de trois mille fois l’âge de l’Univers, quand un algorithme en $n^2$ répond en dix microsecondes.

Un algorithme en $n^2$ tourne sur une machine mille fois plus rapide qu’un algorithme en $n\log_2 n$. Lequel l’emporte ?

Réponse

Le premier fait $n^2/1000$ opérations « à l’échelle » du second, qui en fait $n\log_2 n$. Il gagne tant que $n<1000\log_2 n$, c’est-à-dire jusqu’à $n\approx 14\,000$. Au-delà, il perd, et de plus en plus nettement : pour $n=10^9$, il est déjà 30 000 fois plus lent. Une meilleure classe de complexité finit toujours par battre une meilleure machine.

Une échelle de raffinement : la recherche du doublon

La notion de complexité permet de classer des algorithmes réalisant la même tâche, comme dans la vidéo suivante. C’est finalement une sorte d’échelle de raffinement ; descendre d’un barreau la complexité temporelle ou spatiale demande le plus souvent de pousser la réflexion plus loin, voire de repenser entièrement le problème. Et c’est ainsi qu’une recherche de doublons dans une liste se transforme en chasse aux cycles sur un graphe dans l’ultime mouture pour atteindre le Graal ($\mathcal{O}(n)$ en temps et $\mathcal{O}(1)$ en espace sans mutation).

Le problème. Un tableau t contient $n+1$ entiers, tous compris entre $1$ et $n$. Il y a forcément un doublon : c’est le principe des tiroirs, $n+1$ chaussettes rangées dans $n$ tiroirs obligent un tiroir à en contenir deux. Comment le trouver ? Tous les codes ci-dessous sont exécutables et modifiables, et travaillent sur le même exemple.

Barreau 1 : comparer toutes les paires

La solution de premier jet : comparer chaque élément à tous ceux qui le suivent. Il y a $\binom{n+1}{2}$ paires, d’où un temps en $\mathcal{O}(n^2)$, mais aucune mémoire supplémentaire.

Barreau 2 : trier d’abord

Une fois le tableau trié, deux valeurs égales sont voisines : un seul passage suffit à les repérer. Le tri coûte $\mathcal{O}(n\log n)$ et domine le reste. On a gagné une classe en temps, mais à un prix : soit on trie une copie, qui occupe $\mathcal{O}(n)$ de mémoire, soit on trie sur place, et l’on modifie les données.

Barreau 3 : se souvenir de ce qu’on a vu

Un ensemble (une table de hachage) répond en temps constant, en moyenne, à la question « ai-je déjà vu cette valeur ? ». Un seul passage suffit : temps $\mathcal{O}(n)$. C’est l’échange le plus classique de l’algorithmique : on achète du temps avec de la mémoire, ici $\mathcal{O}(n)$.

Barreau 4 : le tableau comme mémoire

Les valeurs sont comprises entre $1$ et $n$, et le tableau a des cases numérotées de $0$ à $n$ : chaque valeur $x$ désigne une case. Pour « se souvenir » qu’on a vu $x$, on peut donc marquer la case $x$, en changeant le signe de son contenu. Plus besoin d’ensemble : temps $\mathcal{O}(n)$, mémoire $\mathcal{O}(1)$. Mais c’est une ruse : on a modifié les données, ce qui est souvent interdit (elles peuvent être en lecture seule, ou partagées).

Barreau 5 : chercher parmi les valeurs, pas parmi les cases

Reprenons le principe des tiroirs, mais sur un intervalle de valeurs. Si plus de $m$ éléments du tableau tombent dans un intervalle qui ne contient que $m$ valeurs, le doublon s’y trouve. On coupe l’intervalle $[1,n]$ en deux, on compte combien d’éléments tombent dans la moitié gauche, et l’on garde la moitié « trop peuplée ». C’est une dichotomie : $\log_2 n$ étapes, chacune lisant tout le tableau. Temps $\mathcal{O}(n\log n)$, mémoire $\mathcal{O}(1)$, et cette fois sans toucher aux données. On a reculé d’un barreau en temps pour respecter l’entrée.

Barreau 6 : changer de regard, le tableau est un graphe

Peut-on tout avoir à la fois : temps linéaire, mémoire constante, données intactes ? Oui, à condition de changer complètement de point de vue. Voyons le tableau comme une fonction : la case $i$ pointe vers la case t[i]. Partons de la case $0$, vers laquelle personne ne pointe puisque les valeurs valent au moins $1$, et suivons les flèches : $0\to$ t[0] $\to$ t[t[0]] $\to\cdots$ Comme il n’y a qu’un nombre fini de cases, on finit par repasser par une case déjà visitée. Le chemin dessine alors un ρ : une queue, puis une boucle.

L’entrée de la boucle est une case vers laquelle pointent deux flèches : celle de la queue et celle qui referme la boucle. Deux cases contiennent donc cette valeur : c’est le doublon. Chercher un doublon dans un tableau, c’est chercher l’entrée d’un cycle dans un graphe.

Pour la trouver sans rien mémoriser, on lâche deux coureurs depuis la case $0$ : une tortue qui avance d’un pas à la fois, et un lièvre qui en fait deux. Une fois tous deux dans la boucle, le lièvre gagne une case par pas sur la tortue : il finit par la rattraper. On renvoie alors la tortue au départ, et chacun avance d’un pas : ils se retrouvent exactement à l’entrée de la boucle.

Pourquoi la phase 2 tombe-t-elle pile sur l'entrée ?

Notons $\mu$ la longueur de la queue et $\lambda$ celle de la boucle. Supposons que la rencontre ait lieu après $k$ pas : la tortue a fait $k$ pas, le lièvre $2k$. Ils sont sur la même case de la boucle, donc la différence $2k-k=k$ est un multiple de $\lambda$.

Lors de la phase 2, après $\mu$ pas, la tortue (repartie de $0$) arrive à l’entrée de la boucle. Le lièvre, parti de la case atteinte après $k$ pas, se trouve alors à la case atteinte après $k+\mu$ pas : c’est l’entrée, plus $k$ pas, c’est-à-dire un nombre entier de tours de boucle. Il est donc lui aussi à l’entrée : ils se rencontrent là, et nulle part avant, puisque la tortue n’est pas encore dans la boucle.

BarreauIdéeTempsMémoire en plusDonnées intactes ?
1toutes les paires$\mathcal{O}(n^2)$$\mathcal{O}(1)$oui
2trier, puis comparer les voisins$\mathcal{O}(n\log n)$$\mathcal{O}(n)$ ou $\mathcal{O}(1)$ sur placenon, si l'on trie sur place
3ensemble des valeurs vues$\mathcal{O}(n)$$\mathcal{O}(n)$oui
4marquer les cases par le signe$\mathcal{O}(n)$$\mathcal{O}(1)$non
5dichotomie sur les valeurs$\mathcal{O}(n\log n)$$\mathcal{O}(1)$oui
6lièvre et tortue sur le graphe$\mathcal{O}(n)$$\mathcal{O}(1)$oui
Floyd, Pollard et le paradoxe des anniversaires

L’algorithme du lièvre et de la tortue est attribué à Robert Floyd, sans qu’on lui connaisse de publication : Donald Knuth le mentionne à la fin des années 1960 dans The Art of Computer Programming. Il a trouvé son application la plus spectaculaire en arithmétique. En 1975, John Pollard l’utilise pour factoriser des entiers : on itère une fonction comme $x\mapsto x^2+1$ modulo le nombre à factoriser, et le chemin obtenu dessine, lui aussi, un ρ, d’où le nom de « méthode rho de Pollard ». Le paradoxe des anniversaires garantit que la boucle arrive vite, après environ la racine carrée du nombre de valeurs possibles. En 1980, Richard Brent et Pollard factorisent ainsi le huitième nombre de Fermat, $2^{256}+1$.

En bref
  • Chaque barreau gagne quelque chose : du temps, de la mémoire, ou le respect des données.
  • Le barreau 3 achète du temps avec de la mémoire, grâce à la bonne structure de données.
  • Le barreau 4 « triche » en réutilisant l’entrée comme mémoire ; le barreau 5 change ce que l’on cherche (des valeurs au lieu de positions).
  • Le dernier barreau vient d’un autre domaine : un tableau est aussi un graphe, et un doublon, l’entrée d’un cycle.

Quatre algorithmes, quatre classes : le plus grand sous-tableau

L’échelle du doublon n’est pas une exception. Voici un autre problème, tout aussi simple à énoncer, dont l’histoire est racontée par Jon Bentley dans ses Programming Pearls, et où chaque idée nouvelle fait gagner exactement une classe de complexité.

Le problème. On dispose d’un tableau de nombres, positifs et négatifs, par exemple les gains et pertes quotidiens d’une action. Quelle est la plus grande somme d’une tranche (une suite de cases consécutives) ? Par convention, la tranche vide, de somme $0$, est permise : si tout est négatif, mieux vaut ne rien acheter.

Une course de quelques années

En 1977, Ulf Grenander, statisticien à l’université Brown, cherche des motifs dans des images numérisées. Il ramène son problème à cette version à une dimension, écrit un algorithme en $\mathcal{O}(n^3)$, puis l’améliore en $\mathcal{O}(n^2)$. Michael Shamos trouve ensuite, en une nuit, un algorithme « diviser pour régner » en $\mathcal{O}(n\log n)$. Peu après, lors d’un séminaire à Carnegie-Mellon où Shamos raconte cette histoire, le statisticien Jay Kadane trouve en une minute un algorithme linéaire. On ne peut pas faire mieux : il faut au moins lire chaque case une fois.

$\mathcal{O}(n^3)$ : toutes les tranches, chacune recalculée

Il y a environ $n^2/2$ tranches, et le calcul de chaque somme coûte jusqu’à $n$ additions.

$\mathcal{O}(n^2)$ : ne pas recalculer, prolonger

La somme de t[i..j] est celle de t[i..j-1], plus t[j]. Inutile de tout recommencer : il suffit de prolonger la somme précédente. Une boucle disparaît.

$\mathcal{O}(n\log n)$ : diviser pour régner

Coupons le tableau en deux moitiés. La meilleure tranche est soit entièrement à gauche, soit entièrement à droite (deux problèmes deux fois plus petits, résolus récursivement : c’est le principe de la stratégie diviser pour régner), soit à cheval sur le milieu. Ce dernier cas se règle en temps linéaire : c’est la meilleure tranche qui finit au milieu côté gauche, accolée à la meilleure qui commence au milieu côté droit. Le coût vérifie $T(n)=2T(n/2)+\mathcal{O}(n)$, d’où $T(n)=\mathcal{O}(n\log n)$, comme pour le tri fusion.

$\mathcal{O}(n)$ : un seul passage (Kadane)

Changeons de question : au lieu de chercher la meilleure tranche partout, demandons-nous quelle est la meilleure tranche qui se termine à la case courante. Si l’on connaît la réponse pour la case précédente, la nouvelle s’en déduit aussitôt : on prolonge, ou l’on repart de zéro si la somme est devenue négative (un début de somme négatif ne peut que nuire à la suite). C’est de la programmation dynamique réduite à deux variables.

La course

Le programme ci-dessous compte les additions effectuées par les quatre versions sur des tableaux aléatoires de taille croissante. Quand $n$ double, la version cubique fait environ huit fois plus d’additions, la quadratique quatre fois plus, la version « diviser pour régner » un peu plus de deux fois plus, et Kadane exactement deux fois plus.

1001031061098645124096taille du tableau n (échelle logarithmique)nombre d'additionsn³pente 3n²pente 2n log npente ≈ 1npente 1

Nombre d'additions des quatre algorithmes, en échelles logarithmiques sur les deux axes.

Lire une complexité sur un graphe log-log

Si un algorithme fait environ $c\,n^k$ opérations, alors $\log(c\,n^k)=\log c+k\log n$ : en échelles logarithmiques, sa courbe est une droite de pente $k$. La constante $c$ ne fait que la décaler verticalement. On lit donc directement l’exposant sur le graphe : pente 3, pente 2, et pente 1 pour les deux dernières. La courbe en $n\log n$ est à peine plus pentue que celle en $n$ : le facteur $\log n$ croît si lentement qu’il se voit à peine.

En bref
  • $n^3\to n^2$ : réutiliser un calcul au lieu de le refaire.
  • $n^2\to n\log n$ : diviser pour régner.
  • $n\log n\to n$ : changer de question, pour qu’un seul passage suffise (programmation dynamique).
  • On ne peut pas descendre plus bas : il faut au moins lire chaque case une fois.

$\mathrm{P}\stackrel{?}{=}\mathrm{NP}$

La notion de complexité est au centre d’une des plus importantes conjectures des mathématiques : $\mathrm{P}\stackrel{?}{=}\mathrm{NP}$.

Grossièrement, la conjecture revient à se demander si l’ensemble $\mathrm{NP}$ des problèmes dont les solutions sont facilement vérifiables (en temps polynomial) est le même que l’ensemble $\mathrm{P}$ des problèmes faciles (qu’on peut résoudre en temps polynomial).

Prenons l’exemple classique du voyageur de commerce.
Le problème (dans sa version décisionnelle) demande s’il existe un trajet de longueur inférieure à une valeur $K$ passant une et une seule fois par un ensemble de villes. Pour valider une solution, il suffit donc de vérifier que chaque ville est bien là une et une seule fois, calculer la distance et la comparer à $K$. Cela se fait bien sûr en temps polynomial rendant le problème $\mathrm{NP}$.
Par contre, aucun algorithme connu à ce jour ne sait aboutir à la solution en un temps mieux qu’exponentiel…
Or si $\mathrm{P=NP}$, cela voudrait dire qu’un algorithme polynomial existe bel et bien.

Le meilleur algorithme exact connu, celui de Held et Karp (présenté avec la programmation dynamique), reste en $\mathcal{O}(n^2 2^n)$.

La grande majorité des chercheurs se rangent dans le camp pessimiste $\mathrm{P≠NP}$.

La question a été posée formellement en 1971 par Stephen Cook, et indépendamment par Leonid Levin. Elle fait partie des sept « problèmes du millénaire » pour lesquels l’institut Clay promet, depuis 2000, un million de dollars à qui les résoudra.


Tim Roughgarden, Algorithms Illuminated, 4 volumes (Soundlikeyourself Publishing, 2017-2020), et ses cours en ligne.
Jon Bentley, Programming Pearls (Addison-Wesley, 2e éd. 2000), colonne 8 : l’histoire du plus grand sous-tableau.
Donald Knuth, The Art of Computer Programming, vol. 2, section 3.1 : le lièvre et la tortue.