L'algorithmique
Partie 2 sur 3
4Un exemple détaillé : chercher dans une liste
Supposons qu’il faille savoir si un nom figure dans une liste d’un million de personnes. La méthode la plus simple, la recherche séquentielle, compare le nom à chaque élément, du premier au dernier. Elle fonctionne toujours, mais dans le pire des cas, celui où le nom est absent, elle demande un million de comparaisons.
Si la liste est triée, on peut faire infiniment mieux, comme lorsqu’on cherche un mot dans un dictionnaire : on ouvre au milieu, on regarde si le mot cherché se trouve avant ou après, et l’on recommence dans la bonne moitié. C’est la recherche dichotomique (du grec dikhotomia, « division en deux »). Chaque comparaison élimine la moitié des candidats restants.
fonction RechercheDichotomique(L, v) // L est une liste triée
début ← 1
fin ← longueur(L)
tant que début ≤ fin faire
milieu ← début + (fin − début) div 2
si L[milieu] = v alors renvoyer milieu
sinon si L[milieu] < v alors début ← milieu + 1
sinon fin ← milieu − 1
fin tant que
renvoyer « absent »
fin fonction
Le gain est spectaculaire. Comme on divise par deux à chaque étape, il faut au plus 20 comparaisons pour un million d’éléments (220 = 1 048 576), et 33 pour une liste de 8 milliards de noms, soit la population mondiale. Ce nombre s’appelle le logarithme en base 2 de la taille de la liste. Le prix à payer est de maintenir la liste triée.
Que faire si la valeur est absente ? L’algorithme renvoie ici une valeur spéciale, « absent ». Une autre possibilité consiste à signaler une erreur, en langage de programmation on dit « lever une exception », que le programme appelant devra traiter. Une bonne fonction laisse souvent le choix à celui qui l’appelle, par un paramètre : l’absence est-elle normale, ou anormale ?
5Mesurer l’efficacité
5.1La complexité et la notation OApprofondir
Pour comparer des algorithmes indépendamment de la vitesse des machines, on compte le nombre d’opérations élémentaires qu’ils effectuent en fonction de la taille n des données. On ne garde que l’ordre de grandeur, noté avec un O majuscule (« grand O ») : on dit que la recherche séquentielle est « en O(n) » et la recherche dichotomique « en O(log n) ». Cette mesure s’appelle la complexité en temps ; on étudie de même la complexité en mémoire. On distingue aussi le meilleur cas, le cas moyen et le pire cas : un algorithme peut être rapide en général et très lent sur certaines données.
| Complexité | Exemple | n = 10 | n = 1 000 | n = 1 million |
|---|---|---|---|---|
| O(1), constante | Lire une case d’un tableau | 1 ns | 1 ns | 1 ns |
| O(log n), logarithmique | Recherche dichotomique | 3 ns | 10 ns | 20 ns |
| O(n), linéaire | Recherche séquentielle | 10 ns | 1 µs | 1 ms |
| O(n log n) | Bons algorithmes de tri | 33 ns | 10 µs | 20 ms |
| O(n2), quadratique | Tri par sélection | 100 ns | 1 ms | 17 min |
| O(2n), exponentielle | Essayer toutes les combinaisons | 1 µs | hors de portée | hors de portée |
Le tableau montre pourquoi le choix de l’algorithme compte souvent plus que la puissance de la machine. Quant aux algorithmes exponentiels, aucun progrès matériel ne les sauvera : pour n = 1 000, 2n opérations prendraient infiniment plus longtemps que l’âge de l’Univers.
5.2Les algorithmes de triApprofondir
Trier est l’une des opérations les plus fréquentes en informatique : elle prépare les recherches rapides, l’affichage, la détection des doublons. C’est aussi le terrain d’entraînement favori de l’algorithmique, car de nombreuses méthodes y conduisent, avec des performances très différentes.
- Le tri par sélection cherche le plus petit élément restant et le place en tête, puis recommence avec le reste. Simple, mais toujours en O(n2).
- Le tri par insertion procède comme un joueur de cartes qui range sa main : il prend les éléments un par un et insère chacun à sa place parmi ceux déjà triés. Il est en O(n2) dans le pire cas, mais très rapide sur une liste presque triée.
- Le tri fusion, décrit par John von Neumann en 1945, coupe la liste en deux, trie chaque moitié par le même procédé, puis fusionne les deux moitiés triées. Il est toujours en O(n log n), mais demande une mémoire supplémentaire.
- Le tri rapide (quicksort), inventé par le Britannique Tony Hoare en 1959, choisit un élément pivot, range à sa gauche les plus petits et à sa droite les plus grands, puis trie chaque côté. Très rapide en moyenne, il peut dégénérer en O(n2) si le pivot est mal choisi.
| Tri | Meilleur cas | Pire cas | Stable | En place |
|---|---|---|---|---|
| Par sélection | O(n2) | O(n2) | non | oui |
| Par insertion | O(n) | O(n2) | oui | oui |
| Fusion | O(n log n) | O(n log n) | oui | non |
| Rapide | O(n log n) | O(n2) | non | oui |
Trier un million de fiches avec une méthode en O(n2) prend de l’ordre d’un quart d’heure ; un tri en O(n log n) le fait en quelques centièmes de seconde. Les langages modernes combinent plusieurs méthodes : Python et Java utilisent Timsort, conçu en 2002 par Tim Peters, qui associe le tri fusion et le tri par insertion pour profiter des portions déjà triées.
5.3Les limites du calculApprofondir
Certains problèmes n’ont aucune solution algorithmique. En 1936, Alan Turing a démontré qu’il est impossible d’écrire un programme capable de dire, pour n’importe quel programme et n’importe quelles données, si ce programme finira un jour son calcul ou tournera indéfiniment. Ce résultat, appelé indécidabilité du problème de l’arrêt, a des conséquences très concrètes, y compris en sécurité (voir le coin cyber).
D’autres problèmes ont une solution, mais semblent ne pas en avoir d’efficace. Pour beaucoup d’entre eux, il est facile de vérifier une solution proposée, mais on ne connaît aucune méthode rapide pour la trouver : c’est le cas, par exemple, du remplissage optimal d’un emploi du temps soumis à de nombreuses contraintes. La question de savoir si ces problèmes, dits NP, peuvent tous être résolus rapidement est l’une des plus grandes énigmes des mathématiques : la question « P = NP ? ». Le Clay Mathematics Institute promet depuis 2000 un million de dollars à qui la résoudra ; elle reste ouverte. La cryptographie moderne repose d’ailleurs sur des problèmes que l’on croit difficiles, comme la décomposition d’un très grand nombre en facteurs premiers.
Face aux problèmes trop difficiles, on se contente souvent de méthodes approchées, les heuristiques, qui donnent rapidement une bonne solution sans garantir la meilleure. Enfin, l’apprentissage automatique a changé la donne : au lieu de décrire chaque règle, on écrit un algorithme qui ajuste lui-même ses paramètres à partir d’exemples.
Pour s’exercer
Exercice 2 : combien de comparaisons ?
Combien de comparaisons faut-il, au plus, pour trouver un élément par recherche dichotomique dans une liste triée de 1 000 éléments ? Et par recherche séquentielle ?
Voir la réponse
29 = 512 est trop petit et 210 = 1 024 suffit : 10 comparaisons au plus par dichotomie. La recherche séquentielle peut en demander 1 000.
Exercice 3 : trier par insertion
Triez la liste 5, 2, 4, 6, 1, 3 par insertion, en écrivant la liste après chaque insertion.
Voir la réponse
On part de 5. On insère 2 : 2, 5. On insère 4 : 2, 4, 5. On insère 6 : 2, 4, 5, 6 (aucun déplacement). On insère 1 : 1, 2, 4, 5, 6 (quatre déplacements). On insère 3 : 1, 2, 3, 4, 5, 6. Le nombre de déplacements dépend du désordre initial : sur une liste déjà triée, il n’y en a aucun.