Complexité asymptotique

Dans cette section, nous allons examiner un aspect extrêmement important d'un algorithme, à savoir sa performance. Même si la vitesse des ordinateurs augmente régulièrement, en fait, elle ne sera jamais assez grande. Les utilisateurs veulent résoudre des problèmes de plus en plus complexes, et pour un grand nombre d'algorithmes, doubler la vitesse de l'ordinateur n'implique pas qu'on puisse résoudre un problème deux fois plus grand.

Il est donc important pour un informaticien de choisir l'algorithme le plus rapide. Il y a là un problème difficile : la vitesse d'exécution d'un algorithme dépend de l'ordinateur (du processeur, du type et de la quantité de mémoire, de l'organisation et la taille du cache et éventuellement de la rapidité du disque). Comment peut-on comparer des algorithmes du point de vue de la performance si l'on ne connaît pas l'ordinateur sur lequel va tourner l'algorithme ?

De plus, le temps d'exécution d'un algorithme dépend bien sûr de la taille du problème à résoudre. Pour comparer deux algorithmes du point de vue de la performance, il faudrait alors donner la taille du problème à résoudre. Le résultat de cette comparaison peut varier selon la taille du problème.

Ces questions sont étudiées par une branche de l'informatique que nous appelons la théorie de la complexité. Nous allons en particulier nous intéresser au concept de complexité asymptotique.

L'idée de base est de ne pas mesurer directement le temps d'exécution d'un algorithme, mais de compter le nombre d'opérations élémentaires (additions, soustractions, comparaisons, etc.) requises par son exécution en fonction de la taille du problème. Nous allons appeler cette fonction la fonction du temps de l'algorithme. Pour un problème de taille $n$, nous allons noter cette fonction $t(n)$. Malheureusement, la fonction du temps ne permet pas forcément de comparer la vitesse d'exécution de deux algorithmes. La raison est qu'une opération élémentaire peut s'exécuter plus ou moins rapidement selon l'ordinateur en question.

Pour contourner ces problèmes, les informaticiens ont inventé la notion de complexité asymptotique. Avec la complexité asymptotique, on ne donne pas la fonction du temps exacte, mais uniquement une approximation de celle-ci. Cette approximation est donnée sous la forme d'une fonction bien connue qui donne la forme générale de la fonction du temps.

Exemple : Prenons un algorithme dont la fonction du temps est $t(n) = 21n^3$. La complexité asymptotique va donner l'approximation $n^3$, i.e., on ne s'occupe pas du facteur constant $21$, mais on regarde uniquement la forme générale de la fonction. Cette approximation permet de ne pas tenir compte de la différence de vitesse entre différents ordinateurs.

La notation utilisée pour indiquer qu'il s'agit d'une approximation de la fonction du temps est appelée la notation grand O , car elle utilise la lettre 'O' majuscule. Donc, on dit qu'un algorithme avec $t(n) = 21n^3$ a une complexité asymptotique (ou simplement une complexité) $O(n^3)$ (prononcer ``grand O de $n$ cube).

La complexité asymptotique ne nous permet donc pas de comparer deux algorithmes différents dont la forme de la fonction est la même. Une telle comparaison ne serait d'ailleurs pas forcément utile, à cause des différences entre les ordinateurs. Par contre, la complexité asymptotique permet de comparer deux algorithmes dont la forme de la fonction du temps est différente.

Exemple : pour trier un tableau de nombres par ordre croissant, il existe un algorithme dont le nom est tri par insertion et dont la complexité est $O(n^2)$. Il en existe un autre dont le nom est tri par tas et dont la complexité est $O(n \mathrm{log} n)$. Lequel est le plus rapide ? En général $n^2 > n \mathrm{log} n$, ce qui indique que le tri par tas est plus rapide que le tri par insertion (en général, c'est le cas). Mais on ne peut pas être sûr. Il est tout à fait possible que pour le tri par insertion $t(n) = 2n^2$ et que pour le tri par tas $t(n) = 1000n \mathrm{log} n$. Heureusement, cette situation n'arrive pratiquement jamais. Il est donc raisonnable de conclure que le tri par tas est plus rapide que le tri par insertion. Ceci est d'autant plus vrai que la taille du problème (la valeur de $n$) est grande. Dans le cas ci-dessus $2n^2$ est supérieur à $1000 n \mathrm{log} n$ à partir de $n = 5000$ environ. Autrement dit, si le tableau à trier a une taille supérieure à $5000$ (ce qui est souvent le cas), l'algorithme de complexité $O(n \mathrm{log} n)$ est plus rapide, même si la constante est $500$ fois plus élevée.

Une grande partie de l'algorithmique est consacrée à trouver des algorithmes efficaces du point de vue de la complexité asymptotique. De plus, on est parfois capable de prouver que l'algorithme trouvé est le plus efficace possible. Dans le cas du tri, par exemple, on peut prouver que si l'on n'utilise que des comparaisons pour déterminer le plus grand de deux nombres, alors, un algorithme ne peut pas avoir une complexité asymptotique inférieure à $O(n \mathrm{log} n)$. Un tel résultat est très important; en effet on ne perdra pas son temps à rechercher un algorithme plus rapide qui n'existe pas.