Compter les opérations

Pourquoi ne pas chronométrer

Deux algorithmes, un même résultat

Il existe presque toujours plusieurs façons de résoudre un même problème. Elles donnent le même résultat, mais pas au même prix. Comment comparer objectivement deux algorithmes ?

La tentation est de les chronométrer. Mais le temps mesuré en secondes dépend de la machine, du langage, de ce que fait l'ordinateur à côté, de la température du processeur... Un algorithme lent sur un vieux téléphone peut sembler rapide sur un serveur récent. Le chronomètre ne mesure pas l'algorithme, il mesure un contexte.

L'idée : compter les opérations, pas les secondes

On préfère compter le nombre d'opérations élémentaires que l'algorithme effectue, en fonction de la taille de l'entrée, notée n. Ce nombre, lui, ne dépend ni de la machine ni du langage : il est intrinsèque à l'algorithme.

def somme(liste):
    total = 0              # (1 operation)
    for x in liste:        # (la boucle tourne n fois)
        total += x         # (1 operation, repetee n fois)
    return total           # (1 operation)

Pour une liste de taille n, cet algorithme effectue environ 1 + n + 1 = n + 2 opérations. Ce qui compte, c'est le terme qui grandit avec n : le n.

Ce qui compte, c'est comment ça grandit

L'intérêt n'est pas de calculer un nombre exact, mais de savoir comment le coût évolue quand n augmente. Si tu doubles la taille de l'entrée, le temps double-t-il ? Est-il multiplié par quatre ? Reste-t-il constant ?

   Algorithme A : ~ n operations       (double n  ->  double le cout)
   Algorithme B : ~ n^2 operations     (double n  ->  x4 le cout)

Pour n = 10, A fait 10 opérations et B en fait 100 — pas dramatique. Mais pour n = 1 000 000, A en fait un million et B en fait mille milliards. La différence n'est plus une question de machine : elle est structurelle.

Le pire cas

Par prudence, on raisonne en général sur le pire cas : le scénario où l'algorithme travaille le plus. Chercher un élément dans une liste peut tomber juste au premier essai (chance) ou exiger de tout parcourir (élément absent). C'est ce dernier, le pire cas, qui donne une garantie fiable.

En résumé