CHAPITRE 1 : POURQUOI LE CHRONOMÈTRE MENT

Vous avez deux programmes qui font la même chose. Lequel est le meilleur ? La réponse paraît simple : on les lance, on chronomètre, et le plus rapide gagne. C'est exactement ce qu'il ne faut pas faire.

Une expérience qui tourne mal

Deux étudiants écrivent chacun un programme qui cherche un nom dans une liste. Awa parcourt la liste du début à la fin. Bello, lui, trie d'abord puis coupe la liste en deux à chaque étape.

Ils testent sur 20 noms. Le programme d'Awa répond en 3 millisecondes, celui de Bello en 11. Awa a gagné, c'est net.

Le lendemain, le professeur teste les deux programmes sur le fichier réel de l'établissement : 40 000 étudiants. Awa met 4 secondes. Bello met 9 millisecondes. Le classement s'est inversé.

Que s'est-il passé ? Rien d'anormal. Le chronomètre n'a pas menti sur ce qu'il mesurait : il a menti sur ce qu'on croyait mesurer.

Ce que le chronomètre mesure vraiment

Quand vous chronométrez un programme, vous mesurez un mélange :

• la méthode employée : la seule chose qui vous intéresse ;
• la vitesse du processeur de la machine du jour ;
• le langage, et la qualité du compilateur ;
• ce que faisait l'ordinateur en même temps ;
• et surtout : la taille des données du test.

Changez n'importe lequel de ces éléments, le verdict change. Une mesure qui dépend de la machine sur laquelle on la prend n'est pas une mesure, c'est une anecdote.

Changer de question

La complexité abandonne la question « combien de temps ? » pour une autre, qui a une réponse stable :

Si les données doublent, le travail double-t-il aussi ? Ou bien quadruple-t-il ?

Reprenons nos deux étudiants avec cette question-là.

• Awa parcourt toute la liste. Deux fois plus de noms, deux fois plus de comparaisons. Le travail suit la taille, proportionnellement.
• Bello coupe en deux à chaque étape. Doubler la liste n'ajoute qu'une seule coupe de plus. Passer de 1 000 à 2 000 noms lui coûte une comparaison supplémentaire. Une.

Cette réponse-là ne dépend ni du processeur, ni du langage, ni de l'humeur du système d'exploitation. Elle est vraie sur un vieux portable comme sur un serveur. C'est elle qu'on appelle la complexité.

Pourquoi cela décide de tout

Un écart de vitesse entre deux machines, c'est un facteur 2, 5, peut-être 10. Un écart de complexité, c'est un facteur qui grandit avec les données. Sur un million d'éléments, la méthode d'Awa demande un million de comparaisons ; celle de Bello en demande vingt.

Aucun processeur ne rattrape cela. Acheter une machine dix fois plus rapide ne vous fera pas gagner le facteur 50 000 qui sépare les deux méthodes. Le choix de l'algorithme pèse plus lourd que le choix du matériel, et c'est le seul des deux qui ne coûte rien.

Ce qu'on va faire dans ce cours

Trois choses, dans cet ordre :

1. Compter le travail d'un algorithme, en fonction de la taille des données.
2. Classer ce compte dans une famille de croissance, avec une notation que tout le monde comprend.
3. Décider : choisir entre deux méthodes, et savoir quand l'optimisation en vaut la peine.