De nombreux outils formels ou théories ont été développés pour décrire les algorithmes, les étudier, exprimer leurs qualités, pouvoir les comparer entre eux :
- Ainsi, pour décrire les algorithmes, des structures algorithmiques ont été mises en évidences : structures de contrôle (boucle, conditionnelle, ...) et structures de données (variables, listes, ...).
- Pour justifier de la qualité des algorithmes les notions de correction, de complétude et de terminaison ont été mises en place.
- Enfin, pour comparer les algorithmes entre eux, une théorie de la complexité des algorithmes a été définie.
Structures algorithmiques
Les concepts en œuvre en algorithmique, par exemple selon l'approche de N. Wirth pour les langages les plus répandus (Pascal, C, etc..), sont en petit nombre, ils appartiennent à deux classes :
- les structures de contrôle
- séquences
- conditionnelles
- boucles
- les structures de données
- constantes
- variables
- tableaux
- structures récursives (listes, arbres, graphes)
Ce découpage est parfois difficile à percevoir pour certains langages (Lisp, Prolog, ...) plus basés sur la notion de récursivité où certaines structures de contrôle sont implicites (et, donc, semblent disparaître).
Correction, complétude, terminaison
Ces trois notions "correction", "complétude", "terminaison" sont liées, et supposent qu'un algorithme est écrit pour résoudre un problème.
La terminaison est l'assurance que l'algorithme terminera en un temps fini. Les preuves de terminaisons font habituellement intervenir une fonction entière positive strictement décroissante à chaque "pas" de l'algorithme.
Étant donnée la garantie qu'un algorithme terminera, la preuve de correction doit apporter l'assurance que si l'algorithme termine en donnant une proposition de solution, alors cette solution est correcte, elle est effectivement une solution au problème posé.
La preuve de complétude garanti que pour un espace de problèmes donné, l'algorithme, s'il termine, donnera des propositions de solutions.
Complexité algorithmique
Les principales notions mathématiques dans le calcul du coût d’un algorithme précis sont les notions de domination (notée O(f(n)), « grand o »), où f est une fonction mathématique de n, variable désignant la quantité d’informations (en bits, en nombre d’enregistrements, etc.) manipulée dans l’algorithme. En algorithmique on trouve souvent des complexités du type :
| Notation | Type de complexité |
|---|
| O(1) | complexité constante (indépendante de la taille de la donnée) |
| O(log(n)) | complexité logarithmique |
| O(n) | complexité linéaire |
| O(nlo**g(n)) | complexité quasi-linéaire |
| O(n) | complexité quadratique |
| O(n) | complexité cubique |
| O(n) | complexité polynomiale |
| O(n) | complexité quasi-polynomiale |
| O(2) | complexité exponentielle |
| O(n!) | complexité factorielle |
Sans entrer dans les détails mathématiques, le calcul de l’efficacité d’un algorithme (sa complexité algorithmique), consiste en la recherche de deux quantités importantes. La première quantité est l’évolution du nombre d’instructions de base en fonction de la quantité de données à traiter (par exemple, pour un algorithme de tri, il s'agit du nombre de données à trier), que l’on privilégiera sur le temps d'exécution mesuré en secondes (car ce dernier dépend de la machine sur laquelle l'algorithme s'exécute). La seconde quantité estimée est la quantité de mémoire nécessaire pour effectuer les calculs. Baser le calcul de la complexité d’un algorithme sur le temps ou la quantité effective de mémoire qu’un ordinateur particulier prend pour effectuer ledit algorithme ne permet pas de prendre en compte la structure interne de l’algorithme, ni la particularité de l’ordinateur : selon sa charge de travail, la vitesse de son processeur, la vitesse d’accès aux données, l’exécution de l’algorithme (qui peut faire intervenir le hasard) ou son organisation de la mémoire, le temps d’exécution et la quantité de mémoire ne seront pas les mêmes.
Il existe également un autre aspect de l'évaluation de l'efficacité d'un algorithme : les performances en moyenne de cet algorithme. Elle suppose d'avoir un modèle de la répartition des données de l'algorithme, tandis que la mise en œuvre des techniques d'analyse implique des méthodes assez fines de combinatoire et d'évaluation asymptotique, utilisant en particulier les séries génératrices et des méthodes avancées d'analyse complexe. L'ensemble de ces méthodes sont regroupées sous le nom de combinatoire analytique.
On trouvera dans l’article sur la théorie de la complexité des algorithmes d’autres évaluations de la complexité qui vont en général au-delà des valeurs proposées ci-dessus et qui répartissent les problèmes (plutôt que les algorithmes) en classes de complexité.
Quelques indications sur l’efficacité des algorithmes
Souvent, l’efficacité d’un algorithme n’est connue que de manière asymptotique, c’est-à-dire pour de grandes valeurs du paramètre n. Lorsque ce paramètre est suffisamment petit, un algorithme de complexité supérieure peut en pratique être plus efficace. Ainsi, pour trier un tableau de 30 lignes (c’est un paramètre de petite taille), il est inutile d’utiliser un algorithme évolué comme le Tri rapide (l’un des algorithmes de tri les plus efficaces en moyenne) : l’algorithme de tri le plus trivial sera suffisamment efficace.
Entre deux algorithmes dont la complexité est identique, on cherchera à utiliser celui dont l’occupation mémoire est la plus faible. L’analyse de la complexité algorithmique peut également servir à évaluer l’occupation mémoire d’un algorithme. Enfin, le choix d’un algorithme plutôt qu’un autre doit se faire en fonction des données que l’on s’attend à lui fournir en entrée. Ainsi, le Quicksort (ou tri rapide), lorsque l’on choisit le premier élément comme pivot, se comporte de façon désastreuse si on l’applique à une liste de valeurs déjà triée. Il n’est donc pas judicieux de l’utiliser si on prévoit que le programme recevra en entrée des listes déjà presque triées.
Un autre paramètre à prendre en compte est la localité de l’algorithme. Par exemple pour un système à mémoire virtuelle qui dispose de peu de mémoire (par rapport au nombre de données à traiter), le Tri rapide sera normalement plus efficace que le Tri par tas car le premier ne passe qu’une seule fois sur chaque élément de la mémoire tandis que le second accède à la mémoire de manière discontinue (ce qui augmente le risque de swapping).
Enfin, il existe certains algorithmes dont la complexité est dite amortie. Cela signifie que, pour certaines exécutions de l’algorithme (cas marginaux), la complexité de l’algorithme sera très supérieure au cas moyen. Bien sûr, on n’utilise la notion de complexité amortie que dans les cas où cette réaction est très marginale.