Complexité des algorithmes
La vitesse d'exécution d'un algorithme est évaluée en fonction de sa complexité. Chaque type de complexité est fonction du nombre d'éléments qui devra être traité. Ces évaluations donnent le temps d'exécution moyen de l'algorithme s'il est appliqué un grand nombre de fois.
Les complexités présentées ci dessous sont classée de la plus lente à la plus rapide. N représente le nombre d'éléments à traiter.
| Complexité | Vitesse | Description | Formulation | Exemple |
|---|---|---|---|---|
| Factorielle | très lent | temps d'exécution proportionnel à NN | N! | Résolution par recherche exhaustive du problème du voyageur de commerce. |
| Exponentielle | lent | temps d'exécution proportionnel à une valeur donnée à la puissance N | KN | Résolution par recherche exhaustive du Rubik's Cube. |
| Polynomiale | moyen | temps d'exécution proportionnel à N à une puissance donnée | NK | Tris par comparaison, comme le tri à bulle (N2). |
| Quasi-linéaire | assez rapide | temps d'exécution intermédiaire entre linéaire et polynomial | N * log(N) | Tris quasi-linéaires, comme le Quicksort. |
| Linéaire | rapide | temps d'exécution proportionnel à N | N | Itération sur un tableau. |
| Logarithmique | très rapide | temps d'exécution moyen proportionnel au logarithme de N | log(N) | Recherche dans un arbre binaire. |
| Constante | le plus rapide | temps d'exécution donné, quel que soit le nombre d'éléments | 1 | Recherche par index dans un tableau. |
Remarque: Chacune des équations dans la colonne "Formulation" est une borne sur le temps d'exécution, donnée à une constante multiplicative près.
[modifier] Analyse de la complexité
Une opération donnée peut avoir des complexités algorithmique différente selon les données qu'elle doit traiter ou leur ordre. Les méthodes d'analyse sont les suivantes :
| Nom | Description | Exemple |
|---|---|---|
| Cas favorable | La durée de l'opération correspond à son minimum théorique. | Le tri à bulle peut s'exécuter en temps linéaire si les éléments à trier sont déjà dans l'ordre. |
| Cas moyen | C'est la durée moyenne de l'opération pour un type des données quelconques. | Le Quicksort a, en général, une complexité en N * log(N). |
| Cas défavorable | La durée de l'opération correspond à son maximum théorique. | Dans le pire des cas, Quicksort a une complexité en N2. |
| Cas défavorable amorti | C'est le cas défavorable appliqué sur une infinité de jeux de données en entrée. | vector::push_back() a une complexité constante (K) pour le cas défavorable amorti. |
Le choix de l'algorithme doit s'effectuer en fonction des cas que le programme est susceptible de rencontrer. Par exemple, une application qui doit se protéger d'entrées malveillantes devra éviter une implémentation naïve de Quicksort, dont la complexité dans le pire des cas est N2, même si c'est la plus rapide dans le cas moyen.
