Voir la source de Analyse de la complexité des algorithmes

[[Fichier:Binary search vs Linear search example svg.svg|vignette|Représentation d'une recherche linéaire (en violet) face à une [[recherche dichotomique]] (en vert). La complexité algorithmique de la seconde est [[Logarithme|logarithmique]] alors que celle de la première est linéaire.]]

L''''analyse de la complexité d'un algorithme''' consiste en l'étude formelle de la quantité de ressources (par exemple de [[complexité en temps|temps]] ou d'[[complexité en espace|espace]]) nécessaire à l'exécution de cet [[algorithme]]. Celle-ci ne doit pas être confondue avec la [[Théorie de la complexité (informatique théorique)|théorie de la complexité]], qui elle étudie la difficulté intrinsèque des [[problème (informatique théorique)|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'époque<ref>D'après Donald Knuth ''The Dangers of Computer Science Theory'', in ''Selected Papers on Analysis of Algorithms'' (CSLI Lecture Notes, no. 102.)
{{ISBN|1-57586-212-3}}, 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.</ref> é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 [[Mémoire de masse|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 [[algorithme de tri|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 [[complexité en temps|temps de calcul]] [[Complexité dans le pire des cas|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 [[Probabilité|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 ''[[Analyse amortie|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.

== Exemple de la recherche dans une liste triée ==
Supposons que le problème posé soit de trouver un nom dans un annuaire téléphonique qui consiste en une liste triée alphabétiquement. On peut s'y prendre de plusieurs façons différentes. En voici deux :
# [[recherche séquentielle|Recherche linéaire]] : parcourir les pages dans l'ordre (alphabétique) jusqu'à trouver le nom cherché.
# [[Recherche dichotomique]] : ouvrir l'annuaire au milieu, si le nom qui s'y trouve est plus loin alphabétiquement que le nom cherché, regarder avant, sinon, regarder après. Refaire l'opération qui consiste à couper les demi-annuaires (puis les quarts d'annuaires, puis les huitièmes d'annuaires, etc.) jusqu'à trouver le nom cherché.

Pour chacune de ces méthodes il existe un pire des cas et un meilleur des cas. Prenons la méthode 1 : 
* Le meilleur des cas est celui où le nom est le premier dans l'annuaire, le nom est alors trouvé instantanément.
* Le pire des cas est celui où le nom est le dernier dans l'annuaire, le nom est alors trouvé après avoir parcouru tous les noms.
Si l'annuaire contient {{formatnum:30000}} noms, le pire cas demandera {{formatnum:30000}} étapes.
La complexité dans le pire des cas de cette première méthode pour <math>n</math> entrées dans l'annuaire fourni est <math>O(n)</math>, cela signifie que dans le pire des cas, le temps de calcul est de l'ordre de grandeur de <math>n</math> : il faut parcourir tous les <math>n</math> noms une fois.

Le second algorithme demandera dans le pire des cas de séparer en deux l'annuaire, puis de séparer à nouveau cette sous-partie en deux, ainsi de suite jusqu'à n'avoir qu'un seul nom. Le nombre d'étapes nécessaire sera le nombre entier qui est immédiatement plus grand que <math>\log_2\, n</math> qui, quand <math>n</math> est {{formatnum:30000}}, est 15 (car <math>2^{15}</math> vaut {{formatnum:32768}}). La complexité (le nombre d'opérations) de ce second algorithme dans le pire des cas est alors <math>O(\log_2\, n)</math>, ce qui veut dire que l'ordre de grandeur du nombre d'opérations de ce pire cas est le logarithme en base <math>2</math> de la taille de l'annuaire, c'est-à-dire que pour un annuaire dont la taille est comprise entre <math>2^{p-1}</math> et <math>2^{p}</math>, il sera de l'ordre de <math>p</math>. On peut écrire aussi bien <math>O(\ln\, n)</math> ou <math>O(\log_2\, n)</math>, car <math>\ln\, n</math> et <math>\log_2\, n</math> ont le même ordre de grandeur.

== Complexité, comparatif ==

Pour donner un ordre d'idée sur les différentes complexités, le tableau ci-dessous présente les différentes classes de complexité, leur nom, des temps d'exécution de référence et un problème de ladite complexité.
Les temps d'exécution sont estimés sur la base d'un accès mémoire de 10 [[Seconde (temps)|nanosecondes]] par étape. Les temps présentés ici n'ont aucune valeur réaliste, car lors d'une exécution sur machine de nombreux mécanismes entrent en jeu. Les temps sont donnés à titre indicatif pour fournir un [[Ordre de grandeur (temps)|ordre de grandeur sur le temps]] nécessaire à l'exécution de tel ou tel algorithme.

{| class=wikitable
|+Ordre de grandeur du temps nécessaire à l'exécution d'un algorithme d'un type de complexité
! scope="col" | Temps
! scope="col" | Type de complexité
!Temps
pour
n = 1
! scope="col" | Temps pour n&nbsp;=&nbsp;5
! scope="col" | Temps pour n&nbsp;=&nbsp;10
! scope="col" | Temps pour n&nbsp;=&nbsp;20
! scope="col" | Temps pour n&nbsp;=&nbsp;50
! scope="col" | Temps pour n&nbsp;=&nbsp;250
! scope="col" | Temps pour n&nbsp;=&nbsp;{{formatnum:1000}}
! scope="col" | Temps pour n&nbsp;=&nbsp;{{formatnum:10000}}
! scope="col" | Temps pour n&nbsp;=&nbsp;{{formatnum:1000000}}
! scope="col" | Problème exemple
|-----
| <math>O(1)</math>
| complexité constante 
|10 ns
|10 ns
|10 ns
|10 ns
|10 ns
|10 ns
|10 ns
|10 ns
|10 ns
| accès à une cellule de [[tableau (structure de données)|tableau]]
|-----
| <math>O(\log(n))</math>
| complexité [[Logarithme|logarithmique]]
|10 ns
|10 ns
|10 ns
|10 ns
|20 ns
|30 ns
|30 ns
|40 ns
|60 ns
| [[recherche dichotomique]]
|-----
| <math>\scriptstyle O(\sqrt{n})</math>
| complexité [[Racine d'un nombre|racinaire]]
|10 ns
|22 ns
|32 ns
|45 ns
|71 ns
|158 ns
|316 ns
|1 µs
|10 µs
| [[test de primalité]] naïf 
|-----
| <math>O(n)</math>
| complexité [[Linéarité|linéaire]]
|10 ns
|50 ns
|100 ns
|200 ns
|500 ns
|2.5 µs
|10 µs
|100 µs
|10 ms
| parcours de [[Liste chaînée|liste]]
|-----
| <math>\scriptstyle O(n\; log^*(n))</math>
| complexité quasi linéaire
|10 ns
|50 ns
|100 ns
|200 ns
|501 ns
|2.5 µs
|10 µs
|100,5 µs
|10,05 ms
| [[triangulation de Delaunay]]
|-----
| <math>O(n\log(n))</math>
| complexité linéarithmique
|10 ns
|40 ns
|100 ns
|260 ns
|850 ns
|6 µs
|30 µs
|400 µs
|60 ms
| [[Algorithme de tri|tris par comparaisons]] optimaux (comme le [[tri fusion]] ou le [[tri par tas]])
|-----
| <math>O(n^{2})</math>
| complexité quadratique (polynomiale)
|100ns
|250 ns
|1 µs
|4 µs
|25 µs
|625 µs
|10 ms
|1 s
|2.8&nbsp;heures
| parcours de tableaux 2D
|-----
| <math>O(n^{3})</math>
| complexité cubique (polynomiale)
|1 µs
|1.25 µs
|10 µs
|80 µs
|1.25 ms
|156 ms
|10 s
|2.7&nbsp;heures
|316 ans
| [[Produit matriciel|multiplication matricielle]] naïve
|-----
| <math>O\left(2^{\rm{poly}(\log(n))}\right)</math>
|  complexité sous-exponentielle
|10ns
|30 ns
|100 ns
|492 ns
|7 µs
|5 ms
|10 s
|3.2 ans
|<math>10^{20}</math>&nbsp;ans 
| [[Décomposition en produit de facteurs premiers|factorisation d’entiers]] avec [[GNFS]] (le meilleur algorithme connu en 2018)
|-----
| <math>O\left(2^{\rm{poly}(n)}\right)</math>
| complexité exponentielle
|20ns
|320 ns
|10 µs
|10 ms
|130 jours
|<math>10^{59}</math>&nbsp;ans 
|...
|...
|...
| [[problème du sac à dos]] par force brute
|-----
| <math>O(n!)</math>
| complexité factorielle
|10ns
|1.2 µs
|36 ms
|771 ans
|<math>10^{48}</math>&nbsp;ans
|...
|...
|...
|...
| [[problème du voyageur de commerce]] avec une approche naïve
|-----
| <math>O\left(2^{2^{\rm{poly}(n)}}\right)</math>
| complexité doublement exponentielle
|400 ns
|4.3 s
| <math>10^{278}</math> ans
|...
|...
|...
|...
|...
|...
| [[arithmétique de Presburger|décision de l'arithmétique de Presburger]]
|}

<math>log^*(n)</math> est le [[logarithme itéré]].

== Notes ==
<references/>

== Bibliographie ==
* {{Langages formels, calculabilité et complexité}}
* {{Computational Complexity (Arora et Barak)}}
* {{Computational Complexity (Papadimitriou)}}
* {{en}} Michael R. Garey et David S. Johnson, ''Computers and Intractability : A guide to the theory of NP-completeness'', W.H. Freeman & Company, 1979 {{ISBN|0-7167-1045-5}}
* Richard Lassaigne et Michel de Rougemont, ''Logique et Complexité'', Hermes, 1996 {{ISBN|2-86601-496-0}}
* Nicolas Hermann et Pierre Lescanne, ''Est-ce que P = NP ?'' Les Dossiers de La Recherche, 20:64–68, août-{{date-|octobre 2005}}

== Voir aussi ==
=== Articles connexes ===
* [[Théorie de la complexité (informatique théorique)]]
* [[Complexité]], article général sur la complexité
* [[Complexité de Kolmogorov]]
* [[Explosion combinatoire]]
* [[Machine de Turing non déterministe]]
* [[Réduction polynomiale]]

{{Palette Informatique théorique}}

{{Portail|informatique|Informatique théorique}}
[[Catégorie:Algorithmique]]
[[Catégorie:Informatique théorique]]
[[Catégorie:Logique mathématique]]
[[Catégorie:Calculabilité]]
[[Catégorie:Théorie de la complexité des algorithmes]]