Complexité d’un algorithme
La complexité est définie comme un maximum : c’est le nombre maximum d’opérations élémentaires nécessaires pour exécuter un algorithme sur une entrée de taille paramétrée par une ou plusieurs variables.
Cela suppose de définir plusieurs choses :
- Une opération élémentaire est traditionnellement une opération qui prend très peu de temps à effectuer par le processeur sur lequel l’algorithme est destiné à être implémenté. Par exemple, une multiplication ou une addition sont souvent considérées comme des opérations élémentaires. Il y a des exceptions à cela ! Par exemple, en cryptographie, on considère souvent des problèmes sur des entiers de très grandes tailles pour lesquels on ne peut plus considérer raisonnablement que ces opérations soient élémentaires.
- La taille de l’entrée d’un algorithme est à définir en fonction du contexte. Par exemple dans le cas du calcul de la somme de deux entiers, la taille est classiquement le logarithme en base 2 du plus grand des deux nombres (nombre de bits pour le coder en mémoire). Dans le cas d’un algorithme sur un graphe, la taille peut être le nombre de sommets, le nombre d’arêtes…
Généralement les complexités sont exprimées en comportement asymptotique (notation O). En effet, bien souvent il est considéré suffisant de connaître ce comportement pour décider si l’algorithme sera assez rapide ou non.
Typiquement les algorithmes rapides sont les algorithmes linéaires ou en O(n log(n)). Les algorithmes en temps polynomial (avec un degré du polynome au moins égal à deux) sont souvent considérés comme raisonnables, selon le domaine applicatif. Les algorithmes dont la complexité est au moins exponentielle sont très peu utilisés en pratique.
Exemple
Considérons l’exemple classique du tri d’un tableau d’entiers : on dispose d’un tableau de N entiers mélangés, qu’on veut trier par ordre croissant.
Un premier algorithme, appelé “tri à bulles”, consiste à parcourir le tableau du début à la fin, et d’échanger le contenu de deux cases si celui de la i+1ème est plus petit que celui de la ième. Après une itération, la plus grande valeur sera “poussée” en fin de tableau. Il suffit donc de recommencer jusqu’à l’avant-dernière case, etc.
Cet algorithme va parcourir au pire des cas N2 fois le tableau (le pire cas étant un tableau trié à l’envers). Sa complexité est donc O(N2).
Il existe de (très) nombreux autres algorithmes de tri, chacun avec sa complexité. Nous n’entrerons pas dans le détail, mais vous pouvez vous renseigner sur la page Wikipédia dédiée aux tris. Entre autres, le “tri fusion” a une complexité au pire cas de O(N log(N)), et est donc dans l’ensemble plus performant que le tri à bulles.
Attention ! N’oubliez pas que la complexité (dans sa définition générale) se mesure par rapport au pire cas possible. Il existe des algorithmes ayant un ou deux cas à problèmes, mais étant très performants en moyenne. Pour plus de détails, vous pouvez regarder cette fiche du cours.
Quelques remarques sur la complexité d’un algorithme
On peut souvent être tenté de comparer les comportements asymptotiques des complexités des algorithmes pour en tirer des conclusions. C’est d’ailleurs pour ça qu’elles sont le plus souvent utilisées, mais parfois le diable est dans les détails.
Cas pire
La complexité d’un algorithme est définie comme le nombre d’opérations élémentaires requises pour le cas le pire. En pratique l’algorithme peut-être rapide dans quasiment tous les cas. Un exemple d’algorithme célèbre ayant cette propriété est le simplexe.
Comportement asymptotique
Prenons deux fonctions de n f et g. On peut tout à fait avoir f(n) = o(g(n)) et pourtant f(n) > g(n) pour tout n < N. En pratique, il arrive que certains algorithmes aient un comportement asymptotique plus favorable mais soient bien plus lents en pratique. Un exemple célèbre est celui du test de primalité.
L’importance des constantes
Les écritures de comportement asymptotique font l’impasse sur les constantes. En particulier on peut écrire 10^(10^(10^10)) n^2 = O(n^2). Pourtant un algorithme dont la complexité est exactement 10^(10^(10^10)) n^2 est 10^(10^(10^10)) fois plus lent qu’un algorithme dont la complexité est exactement n^2.