Théorie de la récursion (théorie de la calculabilité), domaine de la logique mathématique, de l'informatique théorique, fonctions récursives, machine de Turing, lambda-calcul, machine à compteurs, automate cellulaire).
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). Pouvoir les comparer : ainsi, pour décrire les algorithmes, des structures algorithmiques ont été mises en évidence : structures de contrôle et structures de données ; 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, une théorie de la complexité des algorithmes a été définie.
| 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(nlog(n)) | complexité quasi linéaire |
| O(n2) | complexité quadratique |
| O(n3) | complexité cubique |
| O(np) | complexité polynomiale |
| O(nlog(n)) | complexité quasi polynomiale |
| O(2n) | complexité exponentielle |
| O(n!) | complexité factorielle |
