vignette|Comparaison asymptotique des fonctions utilisées en informatique, plus précisément en algorithmique. On voit par exemple que la fonction linéaire () croit plus vite que la fonction logarithme ().
L'analyse de la complexité d'un algorithme consiste en l'étude formelle de la quantité de ressources (par exemple de temps ou d'espace) nécessaire à l'exécution de cet algorithme. Celle-ci ne doit pas être confondue avec la théorie de la complexité, qui elle étudie la difficulté intrinsèque des problèmes, et ne se focalise pas sur un algorithme en particulier.
Histoire Quand les scientifiques ont voulu énoncer formellement et rigoureusement ce qu'est l'efficacité d'un algorithme ou au contraire sa complexité, ils se sont rendu compte que la comparaison des algorithmes entre eux était nécessaire et que les outils pour le faire à l'époqueD'après Donald Knuth The Dangers of Computer Science Theory, in Selected Papers on Analysis of Algorithms (CSLI Lecture Notes, no. 102.) , le tout premier travail de ce qui est maintenant appelé la théorie de la complexité computationnelle est la thèse de Demuth en 1956 : H. B. Demuth, Electronic Data Sorting --PhD thesis, Stanford University (1956)--, 92 pages, Partiellement reproduit in IEEE Transactions on Computer (1985), pp. 296-310. étaient primitifs. Dans la préhistoire de l'informatique (les années 1950), la mesure publiée, si elle existait, était souvent dépendante du processeur utilisé, des temps d'accès à la mémoire vive et de masse, du langage de programmation et du compilateur utilisé.
Une approche indépendante des facteurs matériels était donc nécessaire pour évaluer l'efficacité des algorithmes. Donald Knuth fut un des premiers à l'appliquer systématiquement dès les premiers volumes de sa série The Art of Computer Programming. Il complétait cette analyse de considérations propres à la théorie de l'information : celle-ci par exemple, combinée à la formule de Stirling, montre que, dans le pire des cas, il n'est pas possible d'effectuer, sur un ordinateur classique, un tri général (c'est-à-dire uniquement par comparaisons) de N éléments en un temps croissant avec N moins rapidement que N ln N.
Différentes approches
L'approche la plus classique est donc de calculer le temps de calcul dans le pire des cas.
Il existe au moins trois alternatives à l'analyse de la complexité dans le pire des cas. La complexité en moyenne des algorithmes, à partir d'une répartition probabiliste des tailles de données, tente d'évaluer le temps moyen que l'on peut attendre de l'évaluation d'un algorithme sur une donnée d'une certaine taille. La complexité amortie des structures de données consiste à déterminer le coût de suites d'opérations. L'analyse lisse d'algorithme, plus récente, se veut plus proche des situations réelles en calculant la complexité dans le pire des cas sur des instances légèrement bruitées.
Algorithmes galactiques
Parfois, l'analyse de la complexité d'un algorithme est trompeuse. En effet, on peut trouver un algorithme disposant d'une meilleure complexité asymptotique mais n'étant pas utilisable en pratique car une constante cachée est si grande que l'algorithme ne sera jamais utilisé pour un jeu de donnée trouvé sur Terre.
Méthodologie Afin d'analyser une complexité d'un algorithme s'exécutant sur un ensemble d'instances on procède en plusieurs étapes :
La première consiste à déterminer une fonction de coût , représentant au choix soit le coût en temps, par exemple nombre d'étapes nécessaires, soit le coût en espace, par exemple le nombre d'octets occupés simultanément, de l'exécution de l'algorithme sur l'entrée .
Ensuite, comme l'on veut déterminer le comportement pris par l'algorithme en fonction d'une taille des instances , il faut alors déterminer cette taille des instances . Cela peut par exemple être le nombre de caractères d'une chaîne de caractère.
Après, l'on doit choisir choisir une mesure de coût , afin d'évaluer le coût de l'algorithme en fonction de la taille des instances et non plus des instances elles-mêmes. La mesure la plus utilisée est le coût dans le cas le plus défavorable mais l'on peut aussi choisir le coût dans le cas le plus favorable ou encore le coût moyen.
Enfin, pour comparer le comportement asymptotique de notre mesure de coût et à d'autres mesures, on raisonne alors sur des ordres de grandeurs de croissance. On peut vouloir montrer une majoration , une minoration ou les deux bornes .
Calcul du coût d'un algorithme en fonction de l'instance
Complexité temporelle
Analyser la complexité temporelle d'un algorithme, c'est compter le nombre d'opérations élémentaires réalisées par cet algorithme.
Opérations élémentaires Les opérations élémentaires comme les opérations arithmétiques, les opérations booléennes, les affectations, les conditions de branchement n'ont pas toutes le même coût. Il est alors aussi difficile qu'inutile de chercher à compter de manière exhaustive toutes les opérations élémentaires réalisées par un algorithme sur une instance. Afin d'obtenir un ordre de grandeur intéressant selon le contexte, on sélectionnera les opérations que l'on veut compter.
Pour toute la famille des tri par comparaison, c'est uniquement la métrique du nombre de comparaisons que l'on compte. Pour autant, pour des tris externes, la métrique du nombre d'accès tableau est couramment utilisée.
Analyse amortie
Lorsque l'on calcule le nombre d'opérations élémentaires, le coût, effectuées par une suite d'opérations sur une structure de donnée. Ce coût est donc la somme des coûts des opérations individuelles.
Si l'on dispose d'une estimation du coût dans le cas le plus défavorable, des opérations individuelles, on obtient une majoration du coût total en sommant ces majorations.
Or, très souvent, cette majoration est très grossière, car le cas le plus défavorable « ne se répète pas », il y a une « compensation » de coût au cours de la suite d'opérations.
Une analyse plus précise que la majoration grossière est appelée analyse amortie.
Complexité en espace
La complexité spatiale d'un algorithme représente la quantité de mémoire utilisée par celui-ci, cette quantité est souvent mesurée en nombre d'octet.
Le coût spatial d'une exécution d'un algorithme est la quantité maximale de mémoire utilisée simultanément par cet algorithme au cours de l'exécution.
Détermination de la taille des instances Déterminer la taille d'une entrée c'est compter le nombre de bits ou d'octet occupés par l'entrée.
Pour un graphe , on prendra souvent comme taille du graphe.
Pour n tableau de chacun de taille bits, si la taille réelle est . Pourtant, bien souvent on approximera cette taille à car le terme n'apparaît pas dans l'expression du coût. Cela n'est pas possible pour le tri comptage.
Exemple : le tri par comptage
Dans l'analyse la complexité du tri comptage, sans hypothèses particulières, on peut facilement calculer par mégarde une complexité erronée. En considérant en entrée le tableau de éléments de bits. Si l'on considère que la taille de l'entrée est , on peut alors montrer que l'algorithme est en . Or ce raisonnement est erroné, car le nombre de bits réellement occupés par l'entrée est la complexité de l'algorithme étant alors , exponentielle en la taille de l'entrée. Ce résultat est cohérent, car l'hypothèse particulière du tri comptage, nécessaire à l'établissement de la complexité linéaire, est une majoration du nombre de bits, on retombe alors dans le premier cas.
Mesures du coût d'un algorithme en fonction le la taille des instances Soit un problème et un algorithme qui le résout. Sur une instance de taille , l'algorithme s'exécute sur en un certain nombre d'opérations élémentaires, on appelle ce nombre le cout .
Si le coût d'un algorithme dépend de l'instance d'entrée, elle n'est pas fixée pour une taille donnée. Pour autant, l'objectif est d'évaluer le coût d'un algorithme en fonction de la taille de l'instance. On définit alors trois nuances de fonctions de couts dépendant de ce critère, qui sont des points de repère pour appréhender la complexité réelle.
Coût dans le pire cas
Le coût dans le cas le plus défavorable d'un algorithme pour les instances de taille , noté , est le maximum de ses coûts sur toutes les instances de taille .
Autrement dit,
Coût dans le meilleur cas
Le coût dans le cas le plus favorable d'un algorithme pour les instances de taille , noté , est le minimum de ses coûts sur toutes les instances de taille .
Autrement dit,
Coût moyen
Lorsque le cas le plus défavorable est un cas pathologique, on peut vouloir calculer un coût moyen.
Définition générale Le coût moyen d'un algorithme pour les instances de taille , noté , avec est la probabilité d'apparition de l'instance parmi les instances de sa taille, est donc l'espérance des coûts des instances de taille .
Autrement dit, .
Cas particulier de la distribution uniforme Le plus souvent, on suppose que toutes les instances d'une taille donnée ont la même probabilité d'apparition.
Le coût moyen uniforme d'un algorithme pour les instances de taille , noté , en notant le nombre d'instances de taille , utilise la distribution de probabilité uniforme .
Autrement dit, .
Autres fonctions de coût D'autres fonctions de coût existent comme la complexité générique des algorithmes ou encore l'analyse lisse d'algorithme mais elles sont moins courantes.
Comparaison asymptotique en informatique
Dans l'étude de la complexité d'un algorithme, on s'intéresse à la manière dont la mesure de coût évolue pour des tailles d'instances très grandes. Cette étude du comportement asymptotique de la mesure de coût, est appelée la complexité asymptotique. L'objectif n'étant pas d'obtenir une valeur exacte de cette complexité mais plutôt un ordre de grandeur, on va alors regrouper les différentes fonctions de coûts dans des ensembles exprimant un comportement asymptotique, les notations de Landau.
Les notations de Landau sont un moyen d'exprimer l'ordre de grandeur du nombre d'opérations effectuées ou nécessaires à effectuer par un algorithme pour résoudre un problème. Trois situations sont décrites par ces notations. La plus fréquente, la notation donne une majoration de l'ordre de grandeur. La notation est une minoration de l'ordre de grandeur, et la notation dénote une équivalence sur les ordres de grandeur.
Dans le cadre de la complexité en informatique, on se limite à définir ces notations au voisinage de et pour des fonctions à valeurs positives. Majoration
La notation , « grand O », est couramment utilisée pour montrer qu'un algorithme de fonction de cout ne s'exécute pas, en ordre de grandeur, en plus d'opérations que .
Informellement, on dit que est en lorsque l'on peut majorer par à une constante près.
Par exemple, le tri par insertion est en .
Définition formelle Soit , on désigne par au voisinage de l'ensemble des fonctions de cout positives tels qu'il existe tels que pour tout .
Autrement dit, .
Exemple
Conventions de notation La principale difficulté avec ce concept provient de la convention de notation abusive historique « de Landau » qui veut que l'on écrive ou encore au lieu de .
De la même manière, la convention veut historiquement que l'on écrive au lieu de .
Pour autant, n'implique pas nécessairement que . De même, n'implique pas forcément . Dans les deux cas, l'axiome d'égalité est contredit.
Minoration
La notation caractérise souvent un problème. Elle sert à justifier que tout algorithme résolvant le problème, de fonction de cout , ne s'exécute pas, en ordre de grandeur, en plus d'opérations que .
Informellement, on dit que est en lorsque l'on peut minorer par à une constante près.
Par exemple, le nombre minimum de comparaisons d'un tri par comparaison est en .
Définition formelle Soit , on désigne par au voisinage de l'ensemble des fonctions de cout positives tels qu'il existe tels que pour tout .
Autrement dit, .