Utilisateur:Pparent/algorithme

L' analyse de la complexité des algorithmes étudie formellement la quantité de ressources en temps et en espace nécessitée par l'exécution d'un algorithme donnée. Celle ci ne doit pas être confondue avec la théorie de la complexité algorithmique des problèmes, 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 rendus compte que la comparaison des algorithmes entre eux était nécessaire et que les outils pour le faire à l'époque é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 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.

Il y a également deux autres directions alternatives à l'analyse de la complexité dans le pire cas. La complexité en moyennecomplexité 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.

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 :

1. Recherche linéaire : parcourir les pages dans l'ordre (alphabétique) jusqu'à trouver le nom cherché.
2. 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 cas et un meilleur cas. Prenons la méthode 1 :

• Le meilleur cas est celui où le nom est le premier dans l'annuaire, le nom est alors trouvé instantanément.
• Le pire 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 30 000 noms, le pire cas demandera 30 000 étapes. La complexité dans le pire cas de cette première méthode pour $n$ entrées dans l'annuaire fourni est $O(n)$, ça veut dire que dans le pire cas, le temps de calcul est de l'ordre de grandeur de $n$  : il faut parcourir tous les $n$ 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 $\log _{2}\,n$ qui, quand $n$ est 30 000, est 15 (car $2^{15}$ vaut 32 768). La complexité (le nombre d'opérations) de ce second algorithme dans le pire des cas est alors $O(\log _{2}\,n)$, ce qui veut dire que l'ordre de grandeur du nombre d'opérations de ce pire cas est le logarithme en base $2$ de la taille de l'annuaire, c'est-à-dire que pour un annuaire dont la taille est comprise entre $2^{p-1}$ et $2^{p}$, il sera de l'ordre de $p$. On peut écrire aussi bien $O(\ln \,n)$ ou $O(\log _{2}\,n)$, car $\ln \,n$ et $\log _{2}\,n$ 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 la-dite complexité. Les temps d'exécution sont estimés sur la base d'un accès mémoire de 10 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 sur le temps nécessaire à l'exécution de tel ou tel algorithme.

Ordre de grandeur du temps nécessaire à l'exécution d'un algorithme d'un type de complexité

Temps	Type de complexité	Temps pour n = 5	Temps pour n = 10	Temps pour n = 20	Temps pour n = 50	Temps pour n = 250	Temps pour n = 1 000	Temps pour n = 10 000	Temps pour n = 1 000 000	Problème exemple
$O(1)$	complexité constante	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	10 ns	Accès tableaux
$O(\log(n))$	complexité logarithmique	10 ns	10 ns	10 ns	20 ns	30 ns	30 ns	40 ns	60 ns	Dichotomie
$\scriptstyle O({\sqrt {n}})$	complexité racinaire	22 ns	32 ns	45 ns	71 ns	158 ns	316 ns	1 µs	10 µs
$O(n)$	complexité linéaire	50 ns	100 ns	200 ns	500 ns	2.5 µs	10 µs	100 µs	10 ms	Parcours de liste
$\scriptstyle O(n\;log^{*}(n))$	complexité quasi-linéaire	50 ns	100 ns	200 ns	501 ns	2.5 µs	10 µs	100,5 µs	10 050 µs	Triangulation de Delaunay
$O(n\log(n))$	complexité linéarithmique	40 ns	100 ns	260 ns	850 ns	6 µs	30 µs	400 µs	60 ms	Tris dont le Tri fusion ou le Tri par tas
$O(n^{2})$	complexité quadratique (polynomiale)	250 ns	1 µs	4 µs	25 µs	625 µs	10 ms	1 s	2.8 heures	Parcours de tableaux 2D
$O(n^{3})$	complexité cubique (polynomiale)	1.25 µs	10 µs	80 ms	1.25 ms	156 ms	10 s	2.7 heures	316 ans	Multiplication matricielle non-optimisée.
$2^{\rm {{poly}(\log(n))}}$	complexité sous-exponentielle	30 ns	100 ns	492 ns	7 µs	5 ms	10 s	3.2 ans	$10^{20}$ ans
$2^{\rm {{poly}(n)}}$	complexité exponentielle	320 ns	10 µs	10 ms	130 jours	$10^{59}$ ans	...	...	...	Problème du sac à dos par force brute.
$O(n!)$	complexité factorielle	1.2 µs	36 ms	770 ans	$10^{48}$ ans	...	...	...	...	Problème du voyageur de commerce (avec une approche naïve).
$2^{2^{\rm {{poly}(n)}}}$	complexité doublement exponentielle	4.3 s	$10^{278}$ ans	...	...	...	...	...	...	Décision de l'arithmétique de Presburger

$log^{*}(n)$ est le logarithme itéré.

Bibliographie

• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
• (en) Sanjeev Arora et Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7)
• (en) Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1993 (ISBN 0-201-53082-1)
• (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-octobre 2005

Voir aussi

Articles connexes

• Complexité, article général sur la complexité
• Complexité de Kolmogorov
• Explosion combinatoire
• Machine de Turing non déterministe
• Réduction polynomiale