La complexité asymptotique est un outil important pour déterminer l'efficacité d'une technique de programmation. Avec cet outil, il est possible de déterminer l'évolution du temps d'exécution d'un code en fonction de la quantité de données traitées. Nous nous en servirons donc très souvent.
Mais la complexité asymptotique ne donne pas toute la vérité concernant l'efficacité d'une méthode. Tout d'abord, dans cette mesure de complexité peut se cacher un facteur multiplicatif arbitrairement grand. Ainsi deux méthodes de même complexité peuvent se comporter complètement différemment.
De plus, la complexité asymptotique est analysée dans le pire
des cas. Certaines méthodes sont très rapides en réalité même si
leur complexité est relativement mauvaise. Ceci s'explique par le
fait que les cas difficiles ne produisent pratiquement jamais. L'exemple
peut-être le plus spectaculaire est la méthode du simplexe pour la
résolution de systèmes d'inéquations. La complexité de cette méthode
est en principe exponentielle (). Elle est pourtant plus
rapide en pratique que les méthodes ayant une complexité polynomiale
pour le même problème. La complexité asymptotique moyenne est
parfois une amélioration par rapport à celle du pire des cas, mais pas
toujours. Elle donne en effet une complexité qui n'est pas pénalisée
par un cas éventuellement pathologique, mais elle suppose que tous les
cas d'utilisation sont de probabilité égale, ce qui est rarement le
cas.
En réalité, il faut déterminer un profil d'utilisation
spécifique de l'application. Il n'est souvent pas nécessaire de
déterminer avec exactitude ce profil. On peut souvent se contenter
d'une estimation (en Anglais : intelligent guess). La section 23.3.4
en donne un exemple spectaculaire où la complexité asymptotique
(moyenne ou au pire) est de alors que pour une utilisation normale
elle est de
.
Parfois, des contingeances matérielles comme l'utilisation du cache
peuvent prendre le pas sur la complexité d'une méthode.
Prenons deux méthodes, la première d'une
complexité
et la deuxième d'une complexité
. Si, par exemple, la deuxième méthode nécessite un surplus
de mémoire par rapport à la première tel que le cache soit
essentiellement inutilisé, la deuxième peut facilement coûter un
facteur 20 par rapport à la première (différence de temps d'accès
entre le cache et la mémoire centrale). Avec
cela donne
environ. La première méthode peut donc être
plus rapide si le nombre d'éléments traités est inférieur à 1 million,
ce qui est souvent le cas. Il est donc impossible aujourd'hui
d'ignorer les effets du cache sur la performance. À une échelle
complètement différente, car alors au lieu d'un facteur 20 il
faut prendre un facteur 1 million, il faut aussi considérer le
système de pagination. Une méthode qui nécessite plus de mémoire que
la quantité de mémoire physique disponible va vite nécessiter des
transferts de données entre le disque et la mémoire centrale, avec
d'énormes pénalités sur la performance. Il est donc parfois
avantageux de choisir une méthode nécessitant moins d'espace mémoire
même si sa complexité est supérieure.
Irene DURAND