« Peut-on faire mieux ? » Toute l’algorithmique tient peut-être dans cette question. Tim Roughgarden, dont les livres Algorithms Illuminated inspirent cette page, en fait le mantra du concepteur d’algorithmes, en citant Aho, Hopcroft et Ullman : « Perhaps the most important principle for the good algorithm designer is to refuse to be content » (le principe le plus important est sans doute de ne jamais se contenter de ce qu’on a).
Cette page apprend d’abord à mesurer l’efficacité d’un algorithme sans chronomètre, grâce à la notion de complexité. Elle montre ensuite, sur deux problèmes très simples, comment on la fait progresser pas à pas : à chaque raffinement, on gagne une classe de complexité, en temps ou en mémoire, quitte à changer de regard sur le problème, voire à emprunter une idée à un domaine qui semblait sans rapport. Elle se termine par la plus célèbre des questions ouvertes de l’informatique, $\mathrm{P}\stackrel{?}{=}\mathrm{NP}$.
La page suivante, Stratégies, passe en revue les grandes méthodes de conception qu’on voit ici à l’œuvre : récursivité, diviser pour régner, programmation dynamique, gloutons, et le rôle des structures de données.
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$ ».
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.
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 ?
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.
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.
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.
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.
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)$.
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).
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.
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.
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.
| Barreau | Idée | Temps | Mémoire en plus | Données intactes ? |
|---|---|---|---|---|
| 1 | toutes les paires | $\mathcal{O}(n^2)$ | $\mathcal{O}(1)$ | oui |
| 2 | trier, puis comparer les voisins | $\mathcal{O}(n\log n)$ | $\mathcal{O}(n)$ ou $\mathcal{O}(1)$ sur place | non, si l'on trie sur place |
| 3 | ensemble des valeurs vues | $\mathcal{O}(n)$ | $\mathcal{O}(n)$ | oui |
| 4 | marquer les cases par le signe | $\mathcal{O}(n)$ | $\mathcal{O}(1)$ | non |
| 5 | dichotomie sur les valeurs | $\mathcal{O}(n\log n)$ | $\mathcal{O}(1)$ | oui |
| 6 | lièvre et tortue sur le graphe | $\mathcal{O}(n)$ | $\mathcal{O}(1)$ | oui |
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$.
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.
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.
Il y a environ $n^2/2$ tranches, et le calcul de chaque somme coûte jusqu’à $n$ additions.
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.
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.
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.
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.
Nombre d'additions des quatre algorithmes, en échelles logarithmiques sur les deux axes.
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.
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.