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 , nous allons noter cette
fonction
. 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
. La complexité asymptotique va donner
l'approximation
,
i.e., on ne s'occupe pas du facteur constant
, 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 a une complexité asymptotique (ou
simplement une complexité)
(prononcer ``grand O de
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 . Il en existe un autre dont le nom est
tri par tas et dont la complexité est
.
Lequel est le plus rapide ? En général
, 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
et que pour le tri par tas
.
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
) est grande. Dans le cas ci-dessus
est
supérieur à
à partir de
environ.
Autrement dit, si le tableau à trier a une taille supérieure à
(ce qui est souvent le cas), l'algorithme de complexité
est plus rapide, même si la constante est
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 à
. 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.