L’idée qu’un problème puisse admettre plusieurs solutions algorithmiques, de qualité très inégale, remonte aux tout débuts de l’algorithmique : Euclide donnait déjà, dans les Éléments, un algorithme de calcul du plus grand commun diviseur nettement plus rapide qu’un balayage naïf de tous les diviseurs possibles. Mais c’est au vingtième siècle, avec le développement de l’informatique comme discipline, que la question de mesurer cette efficacité de façon rigoureuse s’est posée : la notation utilisée aujourd’hui pour comparer la croissance de deux fonctions remonte aux travaux du mathématicien allemand Edmund Landau (d’où son nom de « notation de Landau »), reprise et popularisée en informatique par Donald Knuth dans les années 1970.
Le chapitre Correction des algorithmes a établi comment garantir qu’un algorithme calcule bien ce qu’on attend de lui. Cette garantie ne dit cependant rien de sa rapidité : deux algorithmes corrects pour un même problème peuvent avoir des temps d’exécution radicalement différents dès que la taille des données grandit. Ce chapitre introduit les outils qui permettent de quantifier cette différence — la complexité algorithmique — sans avoir à mesurer un temps d’exécution en secondes, dépendant de la machine, du langage, ou de l’implémentation.
Chronométrer l’exécution d’un programme donne un temps qui dépend de la machine, du langage, de la charge du système au moment du test — une information peu utile pour comparer deux algorithmes dans l’absolu. On préfère donc compter un nombre d’opérations élémentaires, indépendant de ces facteurs, et l’exprimer en fonction de la taille des données en entrée.
On appelle opération élémentaire une opération dont le coût est considéré comme constant, indépendant de la taille des données : une affectation, une comparaison, une opération arithmétique sur des nombres de taille fixée (addition, multiplication…), un accès à un élément d’un tableau par son indice, etc.
Ce choix repose sur une idéalisation : par exemple, une multiplication de deux entiers Python de précision arbitraire n’est réellement en coût constant que si leur taille en mémoire reste bornée (voir le chapitre Représentation des entiers pour ce point). On l’ignore ici en supposant que les nombres manipulés restent de taille raisonnable, ce qui est l’hypothèse usuelle retenue ici.
Soit A un algorithme prenant en entrée une donnée de taille n∈N (longueur d’un tableau, d’une chaîne de caractères, valeur d’un entier, etc., selon le contexte). La complexité temporelle de A est la fonction T:N→N qui à n associe le nombre d’opérations élémentaires effectuées par A sur une entrée de taille n.
Pour une taille n fixée, plusieurs entrées sont en général possibles (plusieurs tableaux de longueur n, par exemple), et le nombre d’opérations peut différer de l’une à l’autre. La fonction T telle que définie ici suppose implicitement qu’on a fixé une convention (pire cas, meilleur cas, cas moyen) pour choisir une valeur parmi ces possibilités — la section suivante précise ce point.
Illustrons cette définition sur un exemple simple.
Considérons la fonction suivante, qui calcule la somme des éléments d’une liste de n entiers :
def somme(t):
s = 0
for x in t:
s = s + x
return s
Le corps de la boucle contient une addition et une affectation, soit deux opérations élémentaires, exécutées une fois par itération. La boucle effectue n itérations (une par élément de t), auxquelles s’ajoute l’initialisation s = 0 (une opération) et le renvoi de s. Le nombre total d’opérations élémentaires est donc : T(n)=2n+2 Ce compte exact dépend de choix arbitraires (compte-t-on return comme une opération ? l’itération elle-même ?) — c’est précisément pour s’affranchir de cette dépendance aux détails d’implémentation qu’on introduit la notation étudiée dans la section suivante.
Encore 25 blocs dans ce document. Le reste du programme est écrit de la même main, avec les figures interactives et votre progression.