Applez Nous: +41 22 518 70 00
Mesurer l’efficacité d’un algorithme par son temps d’exécution en secondes est trompeur : ce temps varie selon la puissance du processeur, le système d’exploitation et la charge de la machine. L’informatique théorique recourt donc à la notation grand O (Big-O), qui exprime l’asymptotique du nombre d’opérations requises en fonction de la taille n des données d’entrée dans le pire des scénarios.
| Notation | Appellation | Comportement avec n = 1000 | Exemple typique |
|---|---|---|---|
O(1) |
Constante | 1 opération | Accès index de liste ou dictionnaire |
O(log n) |
Logarithmique | ~10 opérations | Recherche dichotomique dans liste triée |
O(n) |
Linéaire | 1 000 opérations | Parcours simple d’une liste |
O(n log n) |
Quasi-linéaire | ~10 000 opérations | Tri fusion (Merge Sort), Timsort |
O(n²) |
Quadratique | 1 000 000 opérations | Double boucle imbriquée, tri à bulles |
O(2^n) |
Exponentielle | Incalculable (univers) | Fibonacci récursif naïf |
L’optimisation algorithmique exige un arbitrage constant entre temps d’exécution (CPU) et occupation mémoire (RAM). Créer une copie intégrale d’un ensemble de données pour accélérer un calcul requiert O(n) d’espace supplémentaire, tandis qu’un algorithme “en place” (in-place) opère avec O(1) d’espace mémoire annexe.
Synthèse pédagogique : Un ingénieur logiciel compétent ne se demande pas simplement si son code fonctionne, mais comment son code se comportera lorsque le volume de données sera multiplié par dix mille.
