En aucun endroit la norme C++ ne spécifie la manière de réaliser une fonctionnalité. En effet, elle n'impose ni les structures de données, ni les algorithmes à utiliser. Les seules choses qui sont spécifiées par la norme sont les interfaces bien entendu (c'est-à-dire les noms des classes, des objets et les signatures des fonctions et des méthodes) et la sémantique des diverses opérations réalisables. Cependant, la norme C++ ne permet pas de réaliser toutes ces fonctionnalités n'importe comment, car elle impose également des contraintes de performances sur la plupart de ses algorithmes ainsi que sur les méthodes des conteneurs. Ces contraintes sont exprimées généralement en terme de complexité algorithmique, aussi est-il nécessaire de préciser un peu cette notion.
Note : En pratique, les contraintes de complexité imposées par la bibliothèque standard sont tout simplement les plus fortes réalisables. En d'autres termes, on ne peut pas faire mieux que les algorithmes de la bibliothèque standard.
La nature des choses veut que plus un programme a de données à traiter, plus il prend du temps pour le faire. Cependant, certains algorithmes se comportent mieux que d'autres lorsque le nombre des données à traiter augmente. Par exemple, un algorithme mal écrit peut voir son temps d'exécution croître exponentiellement avec la quantité de données à traiter, alors qu'un algorithme bien étudié aurait n'aurait été plus lent que proportionnellement à ce même nombre. En pratique, cela signifie que cet algorithme est tout simplement inutilisable lorsque le nombre de données augmente. Par exemple, le fait de doubler la taille de l'ensemble des données à traiter peut engendrer un temps de calcul quatre fois plus long, alors que le temps d'exécution de l'algorithme bien écrit n'aurait été que du double seulement. Et si le nombre de données est triplé et non doublé, cet algorithme demandera huit fois plus de temps, là où le triple seulement est nécessaire. Si l'on prend quatre fois plus de données, le temps sera multiplié par soixante-quatre. On voit clairement que les choses ne vont pas en s'améliorant quand le nombre de données à traiter augmente...
En réalité, il est relativement rare de considérer le temps d'exécution pour qualifier les performances d'un algorithme. En effet, le calcul du temps d'exécution n'est pas toujours possible d'une part, parce qu'il se base sur des paramètres a priori inconnus, et n'est pas toujours ce qui est intéressant au niveau du coût d'autre part. Pour illustrer ce dernier point, supposons que chaque opération effectuée par l'algorithme coûte une certaine quantité d'énergie. Dans certains contextes, il est plus important de s'intéresser à l'énergie dépensée qu'au temps passé pour effectuer l'ensemble des traitements. Or certaines opérations peuvent prendre relativement peu de temps, mais coûter très cher énergétiquement parlant, et l'optimisation du temps d'exécution ne donne pas forcément la meilleure solution. Un autre exemple est tout simplement celui de la lecture de secteurs sur un disque dur. La lecture de ces secteurs en soi ne prend pas tellement de temps, en revanche le déplacement de la tête de lecture se fait en un temps d'accès considérablement plus grand. Les algorithmes de gestion des entrées / sorties sur disque des systèmes d'exploitation cherchent donc naturellement à diminuer au maximum ces déplacements en réorganisant en conséquence les requêtes de lecture et d'écriture.
Il est donc généralement beaucoup plus simple de compter le nombre d'opérations que les algorithmes effectuent lors de leur déroulement, car cette donnée est bien moins spécifique au contexte d'utilisation de l'algorithme. Bien entendu, toutes les opérations effectuées par un algorithme n'ont pas le même coût dans un contexte donné, et de plus ce coût varie d'un contexte d'utilisation à un autre. La complexité d'un algorithme doit donc toujours s'exprimer en nombre d'opérations élémentaires d'un certain type, étant entendu que les opérations de ce type sont celles qui coûtent le plus cher selon les critères choisis...
Remarquez que les opérations qui sont réalisées par un algorithme peuvent être elles-mêmes relativement complexes. Par exemple, un algorithme qui applique une fonction sur chaque donnée à traiter peut utiliser une fonction inimaginablement complexe. Cependant, cela ne nous intéresse pas dans la détermination de la complexité de cet algorithme. Bien entendu, ce qu'il faut compter, c'est le nombre de fois que cette fonction est appelée, et la complexité de l'algorithme doit se calculer indépendamment de celle de cette fonction. L'opération élémentaire de l'algorithme est donc ici tout simplement l'appel de cette fonction, aussi complexe soit-elle.
Le nombre des opérations élémentaires effectuées par un algorithme est une fonction directe du nombre de données à traiter. La complexité d'un algorithme est donc directement reliée à cette fonction : plus elle croît rapidement avec le nombre de données à traiter, plus la complexité de l'algorithme est grande.
En réalité, la fonction exacte donnant le nombre d'opérations élémentaires effectuées par un algorithme n'est pas toujours facile à calculer. Cependant, il existe toujours une fonction plus simple qui dispose du même comportement que la fonction du nombre d'opérations de l'algorithme quand le nombre de données à traiter augmente. Cette « forme simplifiée » n'est en fait rien d'autre que la partie croissant le plus vite avec le nombre de données, car lorsque celui-ci tend vers l'infini, c'est elle qui devient prédominante. Cela signifie que si l'on trace le graphe de la fonction, sa forme finit par ressembler à celle de sa forme simplifiée lorsque le nombre de données à traiter devient grand.
La formulation complète de la fonction du nombre d'opérations réalisées par un algorithme n'importe donc pas tant que cela, ce qui est intéressant, c'est sa forme simplifiée. En effet, non seulement elle est plus simple (à exprimer, à manipuler et bien évidemment à retenir), mais en plus elle caractérise correctement le comportement de l'algorithme sur les grands nombres. La complexité d'un algorithme est donc, par définition, le terme prépondérant dans la fonction donnant le nombre d'opérations élémentaires effectuées par l'algorithme en fonction du nombre des données à traiter.
Mathématiquement parlant, le fait que la forme simplifiée d'une fonction se comporte comme la fonction elle-même à l'infini se traduit simplement en disant que les termes d'ordre inférieurs sont écrasés par le terme de premier ordre. Par conséquent, si l'on divise une fonction par l'autre, les termes d'ordre inférieur deviennent négligeables et la valeur du rapport tend à se stabiliser vers les grand nombres. Autrement dit, il est possible de trouver deux constantes A et B positives et non nulles telles que, à partir d'une certaine valeur de n, la triple inéquation 0 ≤ A×c(n) ≤ f(n) ≤ B×c(n), dans laquelle c(n) est la forme simplifiée de la fonction f(n), est toujours vérifiée. La fonction f(n) est donc, en quelque sortes, encadrée par deux « gendarmes » qui suivent le même « trajet » : celui de la fonction c(n).
Note : Notez que cette formulation n'utilise pas le rapport des fonctions f(n) et c(n) directement. Elle est donc toujours valide, même lorsque ces deux fonctions sont nulles, ce qui aurait posé des problèmes si l'on avait utilisé un rapport.
En fait, la limite inférieure A×c(n) ne nous intéresse pas spécialement. En effet, seul le coût maximal d'un algorithme est intéressant, car s'il coûte moins cher que prévu, personne ne s'en plaindra... Il est donc courant d'utiliser une formulation plus simple et plus connue des mathématiciens, dans laquelle seule la dernière inéquation est utilisée. On dit alors que la fonction f(n) est en grand O de c(n) (ce qui se note « O(c(n)) »). Cela signifie qu'il existe une constante A telle que, pour toutes les valeurs de n supérieures à une valeur suffisamment grande, la double inéquation 0 ≤ f(n) ≤ A×c(n) est toujours vérifiée.
Note : La notion de grand O permet donc de donner une borne supérieure de la complexité de la fonction. En fait, si f(n) est en O(c(n)), elle l'est pour toutes les fonctions plus grandes que c(n). Toutefois, en général, on cherche à déterminer la plus petite fonction c(n) qui est un grand O de f(n).
Il est évident que si une fonction f(n) dispose d'une forme simplifiée c(n), elle est en O(c(n)). En effet, l'inéquation supérieure est toujours vérifiée, on ne fait ici qu'ignorer la deuxième inéquation de la définition de la forme simplifiée.
Toutes ces notions peuvent vous paraître assez abstraites, mais il est important de bien comprendre ce qu'elles signifient. Il est donc peut-être nécessaire de donner quelques exemples de complexité parmi celles que l'on rencontre le plus couramment.
Tout d'abord, une complexité de 1 pour un algorithme signifie tout simplement que son coût d'exécution est constant, quel que soit le nombre de données à traiter. Notez bien ici que l'on parle de coût d'exécution et non de durée. Le coût est ici le nombre d'opérations élémentaires effectuées par cet algorithme. Les algorithmes de complexité 1 sont évidemment les plus intéressants, mais ils sont hélas assez rares ou tout simplement triviaux.
Généralement, les algorithmes ont une complexité de n, leur coût d'exécution est donc proportionnel au nombre de données à traiter. C'est encore une limite acceptable, et généralement acceptée comme une conséquence « logique » de l'augmentation du nombre de données à traiter. Certains algorithmes sont en revanche nettement moins performants et ont une complexité en n², soit le carré du nombre des éléments à traiter. Cette fois, cela signifie que leur coût d'exécution a tendance à croître très rapidement lorsqu'il y a de plus en plus de données. Par exemple, si l'on double le nombre de données, le coût d'exécution de l'algorithme ne double pas, mais quadruple. Et si l'on triple le nombre de données, ce coût devient neuf fois plus grand. Ne croyez pas pour autant que les algorithmes de ce type soient rares ou mauvais. On ne peut pas toujours, hélas, faire autrement...
Il existe même des algorithmes encore plus coûteux, qui utilisent des exposants bien supérieurs à 2. Inversement, certains algorithmes extrêmement astucieux permettent de réduire les complexités n ou n² en ln(n) ou n×ln(n), ils sont donc nettement plus efficaces.
Note : La fonction ln(n) est la fonction logarithmique, qui est la fonction inverse de l'exponentielle, bien connue pour sa croissance démesurée. La fonction logarithme évolue beaucoup moins vite que son argument, en l'occurrence n dans notre cas, et a donc tendance à « écraser » le coût des algorithmes qui l'ont pour complexité.
Enfin, pour terminer ces quelques notions de complexité algorithmique, sachez que l'on peut évaluer la difficulté d'un problème à partir de la complexité du meilleur algorithme qui permet de le résoudre. Par exemple, il a été démontré que le tri d'un ensemble de n éléments ne peut pas se faire en mieux que n×ln(n) opérations (et on sait le faire, ce qui est sans doute le plus intéressant de l'affaire). Malheureusement, il n'est pas toujours facile de déterminer la complexité d'un problème. Il existe même toute une classe de problèmes extrêmement difficiles à résoudre pour lesquels on ne sait même pas si leur solution optimale est polynomiale ou non. En fait, on ne sait les résoudre qu'avec des algorithmes de complexité exponentielle (si vous ne savez pas ce que cela signifie, en un mot, cela veut dire que c'est une véritable catastrophe). Cependant, cela ne veut pas forcément dire qu'on ne peut pas faire mieux, mais tout simplement qu'on n'a pas pu trouver une meilleure solution, ni même prouver qu'il y en avait une ! Toutefois, tous ces problèmes sont liés et, si on trouve une solution polynomiale pour l'un d'entre eux, on saura résoudre aussi facilement tous ses petits camarades. Ces problèmes appartiennent tous à la classe des problèmes dits « NP-complets ».
| Précédent | Sommaire | Suivant |
| Gestion personnalisée de la mémoire : les allocateurs | Niveau supérieur | Les types complémentaires |