Compter les opérations

La notation Grand-O

Ne garder que l'essentiel

Compter précisément 3n^2 + 5n + 8 opérations, c'est trop de détails. Quand n devient grand, seul le terme le plus fort compte vraiment. La notation Grand-O (notée O, la lettre O comme « ordre de grandeur ») formalise cette idée : on garde le terme dominant et on jette le reste.

Deux règles de simplification :

   3n^2 + 5n + 8       ->   O(n^2)    (on ne garde que le plus fort terme)
        7n             ->   O(n)      (on jette la constante 7)

On ignore les constantes multiplicatives : 7n et n grandissent de la même façon (doubler n double les deux). On écrit O(n) pour les deux.
On ne garde que le terme dominant : dans n^2 + n, le n^2 écrase le n dès que n est grand. On écrit O(n^2).

Pourquoi ces simplifications sont légitimes

L'objectif du Grand-O est de décrire le comportement à grande échelle, pas de prédire un temps exact. Or à grande échelle, un algorithme en 100n reste infiniment préférable à un algorithme en n^2 :

   n = 10 000 :
     100 n   = 1 000 000        (un million)
     n^2     = 100 000 000      (cent millions)

Même avec une constante de 100, le O(n) gagne largement. La constante devient négligeable devant la façon dont le terme grandit. C'est pour ça qu'on peut se permettre de l'ignorer.

Lire une boucle

En pratique, on lit la complexité directement dans la structure du code :

# O(1)  : (cout constant, independant de n)
x = liste[0]

# O(n)  : (une boucle qui parcourt les n elements)
for x in liste:
    traiter(x)

# O(n^2) : (une boucle imbriquee dans une autre)
for x in liste:
    for y in liste:
        traiter(x, y)      # (execute n x n = n^2 fois)

Une boucle imbriquée dans une autre multiplie les coûts : deux boucles sur n donnent O(n^2), trois donnent O(n^3). Deux boucles l'une après l'autre (non imbriquées) s'additionnent : O(n) + O(n) = O(2n) = O(n).

Ce que O ne dit pas

Le Grand-O décrit une tendance, pas une valeur. Il ne dit pas qu'un O(n) est toujours plus rapide qu'un O(n^2) pour un petit n précis (les constantes cachées peuvent inverser le classement sur de petites entrées). Il dit qu'à partir d'une certaine taille, et pour toujours ensuite, le O(n) l'emporte. C'est une garantie sur le passage à l'échelle.

En résumé