Complexité algorithmique
NSI Première
Définition
La complexité algorithmique mesure la quantité de ressources (le plus souvent le temps, exprimé en nombre d'opérations élémentaires) nécessaires à un algorithme en fonction de la taille des données $n$. On l'exprime avec la notation de Landau $O(\cdot)$, qui décrit l'ordre de grandeur du coût lorsque $n$ devient grand. Elle permet de comparer l'efficacité de deux algorithmes indépendamment de la machine.
Formule
$$O(1) \;<\; O(\log n) \;<\; O(n) \;<\; O(n\log n) \;<\; O(n^2) \;<\; O(2^n)$$
Exemple corrigé
Énoncé
Déterminer la complexité temporelle, en nombre de comparaisons, de la recherche séquentielle d'une valeur dans un tableau de $n$ éléments (dans le pire des cas).
Solution
Dans le pire des cas (valeur absente ou en dernière position), il faut parcourir tout le tableau : on effectue une comparaison par élément.
```python
def recherche(T, cible):
for i in range(len(T)): # n itérations au pire
if T[i] == cible: # 1 comparaison par tour
return i
return -1
```
Le nombre de comparaisons est au plus $n$, soit une croissance proportionnelle à $n$. La complexité est donc linéaire :
$\boxed{O(n)}$
(À comparer à la recherche dichotomique en $O(\log n)$, bien plus rapide.)
Erreurs classiques
- Confondre la taille des données $n$ avec la valeur des données : la complexité dépend du nombre d'éléments, pas de leur grandeur.
- Croire qu'une constante change l'ordre de grandeur : $O(2n)$ et $O(n)$ sont la même complexité linéaire.
Pour aller plus loin : le chapitre « Algorithmique » (cours et exercices corrigés).