Recherche séquentielle et dictionnaires
Cours · informatique (tronc commun des prépas scientifiques), chapitre 2 · prépas scientifiques, tronc commun · le début du chapitre, la suite sur Adloun
2.1 Introduction et motivation
Chercher : voilà sans doute l'opération la plus exécutée de toute l'informatique. Un nom dans un répertoire, un mot dans un texte, le plus grand échantillon d'une série de mesures — derrière chacune de ces questions se cache un parcours de tableau, l'algorithme le plus simple qui soit et pourtant le premier où tout se joue : la spécification du chapitre 1 s'y applique, l'invariant y fait sa première vraie preuve, et une question nouvelle surgit — combien de temps cela prend-il ?
Ce chapitre installe donc le second pilier du cours : la complexité, c'est-à-dire l'estimation asymptotique du coût d'un algorithme dans le cas le pire. On y rencontre les deux premières classes de coût — constant et linéaire — et un personnage qui les illustre à merveille : le dictionnaire de Python, utilisé en boîte noire, qui retrouve une valeur en temps constant là où le tableau exige un parcours complet.
2.2 Le coût d'un algorithme
2.2.1 Compter quoi, et dans quel cas ?
Le coût d'une exécution est le nombre d'opérations élémentaires effectuées : affectations, comparaisons, opérations arithmétiques, accès à une case de tableau — chacune comptée pour un temps constant. On exprime ce coût en fonction de la taille de l'entrée (notée : longueur du tableau, nombre de caractères du texte, etc.).
Pour une taille donnée, toutes les entrées ne coûtent pas le même prix : chercher un élément placé en tête est immédiat, le chercher en vain oblige à tout lire. Le programme retient le coût dans le cas le pire :
C'est une garantie : aucune entrée de taille ne coûtera davantage. Un algorithme rapide « en général » mais catastrophique sur certaines entrées ne vaut rien pour qui doit s'engager sur un temps de réponse.
2.2.2 L'estimation asymptotique
Compter les opérations une à une est aussi fastidieux qu'inutile : entre et opérations, la différence relève du détail d'implémentation — du langage, de la machine. Ce qui compte est le comportement quand grandit : doubler la taille de l'entrée double-t-il le temps, le quadruple-t-il, ou ne change-t-il presque rien ?
Soient et deux fonctions de dans . On dit que s'il existe une constante et un rang tels que
Autrement dit : à une constante multiplicative près, ne croît pas plus vite que . Ainsi , : les deux algorithmes correspondants ont le même comportement asymptotique, dit linéaire.
La notation jette volontairement deux informations : les constantes multiplicatives et les termes d'ordre inférieur. On écrit donc aussi bien pour que pour opérations ; et , car pour grand le terme écrase le reste. Cette perte est un gain : elle rend la mesure indépendante de la machine et du langage, et ne retient que la nature de l'algorithme.
- Un traitement est à coût constant, noté , si son nombre d'opérations est borné indépendamment de : accéder à
t[i], comparer deux nombres, affecter une variable. - Un algorithme est à coût linéaire, noté , si son coût dans le cas le pire est au plus proportionnel à : c'est la signature d'un nombre borné de parcours du tableau.
