Complexité asymptotique et autres facteurs

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 ($O(2^n)$). 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 $O(n)$ alors que pour une utilisation normale elle est de $O(1)$.

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é $O(n \texttt{log} n)$ et la deuxième d'une complexité $O(n)$. 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 $\texttt{log} n = 20$ cela donne $n = 1000000$ 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.