Complexité algorithmique

Complexité algorithmique

Pourquoi mesurer ?

Deux algorithmes peuvent résoudre le même problème avec des temps de calcul radicalement différents. La complexité mesure la croissance du nombre d'opérations en fonction de la taille de l'entrée $n$, indépendamment du matériel.

Notation grand O

On écrit $T(n) = O(f(n))$ quand il existe $c > 0$ et $n_0$ tels que $T(n) \le c \cdot f(n)$ pour tout $n \ge n_0$. On ignore les constantes et les termes négligeables : $3n^2 + 5n + 7 = O(n^2)$.

On distingue :

• pire cas (worst case) : majorant garanti,
• meilleur cas (best case) : minorant,
• cas moyen : moyenne pondérée selon une distribution d'entrées.

Classes usuelles

Notation	Nom	Exemple
$O(1)$	constante	accès tableau
$O(\log n)$	logarithmique	recherche dichotomique
$O(n)$	linéaire	recherche séquentielle
$O(n \log n)$	quasi-linéaire	tri fusion
$O(n^2)$	quadratique	tri par sélection
$O(n^3)$	cubique	produit matriciel naïf
$O(2^n)$	exponentielle	recherche exhaustive
$O(n!)$	factorielle	énumération de permutations

Mesurer en pratique

On compte les opérations « coûteuses » (comparaisons, affectations, accès mémoire). Pour une boucle imbriquée :

for i in range(n):       # n itérations
    for j in range(n):   # n itérations
        T[i][j] = 0      # opération constante

Total : $n \times n = n^2$ opérations, donc $O(n^2)$.

Complexité spatiale

Mémoire supplémentaire utilisée. Un tri en place est $O(1)$ en espace, un tri fusion est $O(n)$.

Décidabilité et complexité

Tous les problèmes ne sont pas résolubles : le problème de l'arrêt est indécidable. Parmi les problèmes décidables, ceux dont on ne connaît aucun algorithme polynomial sont dits « difficiles » (classe NP-difficile : voyageur de commerce, sac à dos 0/1, SAT…).