Algorithme (mathématicien Al-Khwârizmî), latinisé au Moyen Âge en Algoritmi), au IXe siècle écrivit le premier ouvrage systématique, solutions aux équations linéaires et quadratiques.
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 |
