Du constant à l'exponentiel

Une échelle de complexités

Presque tous les algorithmes courants tombent dans une poignée de classes. Les voici, de la plus rapide à la plus lente :

Notation	Nom	Exemple typique
O(1)	constant	accéder à liste[i]
O(log n)	logarithmique	recherche dichotomique, ABR équilibré
O(n)	linéaire	parcourir une liste
O(n log n)	quasi-linéaire	les bons tris (fusion, rapide)
O(n^2)	quadratique	tri à bulles, boucles imbriquées
O(2^n)	exponentiel	essayer toutes les combinaisons

Les visualiser : l'explosion des courbes

Le plus parlant est de dessiner comment le coût grandit avec n. Plus la courbe monte vite, pire c'est.

  cout
   ^
   |                                             . 2^n  (mur vertical)
   |                                          .
   |                                       .
   |                                    .        n^2
   |                                .        _.-'
   |                            . _.-''''
   |                       _.-'''         ______ n log n
   |                 _.-'''      ________/________ n
   |            _.-'''  ________/
   |       _.-'_______/                _____________ log n
   |  _.-''_______________________________________ 1
   +------------------------------------------------> n

O(1) et O(log n) restent quasi plats : ils encaissent des entrées gigantesques sans broncher. O(2^n) grimpe si vite qu'il devient un mur infranchissable dès quelques dizaines d'éléments.

Le tableau qui fait mal

Traduisons en nombre d'opérations pour différentes tailles. Une opération étant supposée durer une nanoseconde :

     n  |  log n |     n     |  n log n  |    n^2      |         2^n
  ------+--------+-----------+-----------+-------------+---------------------
    10  |   ~3   |    10     |    ~33    |    100      |        1 024
   100  |   ~7   |   100     |   ~664    |  10 000     |   ~10^30 (!!!)
  1 000 |  ~10   |  1 000    |  ~9 966   | 1 000 000   |   inimaginable

Regarde la colonne 2^n : pour n = 100, elle atteint 10^30 opérations. Même à un milliard d'opérations par seconde, cela demanderait bien plus que l'âge de l'univers. Un algorithme exponentiel est inutilisable au-delà d'une trentaine d'éléments.

La leçon fondamentale

Améliorer la classe de complexité vaut infiniment mieux qu'optimiser les détails. Passer de O(n^2) à O(n log n) sur un million d'éléments, c'est passer de mille milliards d'opérations à vingt millions : un facteur 50 000. Aucune optimisation de constante (« mon code va 2x plus vite ») ne rivalise avec un changement de classe.

En résumé

Les algorithmes se rangent dans quelques classes, de O(1) (constant, idéal) à O(2^n) (exponentiel, catastrophique). L'écart entre ces classes explose avec n : un O(log n) avale des milliards d'éléments, un O(2^n) cale dès la trentaine. Changer de classe de complexité est le levier de performance le plus puissant qui soit.