Comprendre la notation Big O en 7 minutes

La notation Big O est une notion souvent complètement ignorée par les développeurs. C’est pourtant une notion fondamentale, plus qu’utile et simple à comprendre. Contrairement à l’idée reçue, y’a pas besoin d’être une tronche en math pour la maîtriser. Je te parie qu’en 7 minutes, tu vas tout comprendre.

C’est quoi la notation Big O ?

La notation Big O (ou complexité algorithmique) est une manière standard de mesurer la performance d’un algorithme. C’est une manière mathématique de juger de l’efficacité de ton code. J’ai dit le mot mathématique et j’ai fait fuir tout le monde. Encore une fois, pas besoin d’avoir fait mathsup’ mathspé’ pour comprendre et utiliser cette notation.

Cette notation va te permettre de mesurer l’évolution du taux de croissance de ton algo par rapport aux données d’entrées. Ça va décrire le pire cas possible au niveau de la performance de ton code. Aujourd’hui, on ne va pas parler de complexité en espace, mais seulement de complexité en temps.

Et ça va plus loin que simplement mettre un timer avant et après une fonction pour voir combien de temps ça prend.

D’ailleurs, le problème avec la technique du simple timer c’est que c’est tout sauf fiable et précis. Avec un simple timer les performances de ton algo vont grandement changer selon plein de facteurs.

1. Selon ta machine et tes processeurs
2. Selon le langage que tu utilises
3. Selon la charge d’utilisation de ta machine quand tu lances ton test

La notation Big O règle tous ces problèmes et nous permet d’avoir une mesure fiable de l’efficacité de tout le code que tu produis. Le O de Big O est un petit nom pour « ordre de grandeur ».

Et c’est vraiment le truc important à comprendre. On ne mesure pas directement la vitesse d’un algorithme en secondes. On mesure le taux de croissance d’un algorithme via le nombre d’opérations qu’il faut pour terminer. C’est avec cette notation que la performance d’une solution est discutée entre développeurs.

C’est pas clair mon affaire ? OK, mettons-nous en situation !

Ça pourrait t’arriver

Imagine, t’es au boulot peinard, et un jour on te demande de faire une fonction qui va renvoyer la somme de tous les chiffres partant de 1 jusqu’au nombre passé en paramètre. Plus clairement, quelque chose qui aurait ce comportement.

n = 3

output = getSum(n)

print(output)
# will print : 6  because 1 + 2 + 3 = 6

Immédiatement, la première chose qui te vient à l’esprit c’est de faire une simple boucle qui va cumuler les chiffres un par un. Je te fais les exemples en Python, mais on s’en carre le cul du langage. Ça s’applique pour n’importe quel langage.

def getSum(n):
    sum = 0

    for number in range(1, n + 1):
        sum += number

    return sum

Et ça marche. Tu lances ta fonction avec l’input 3 : instantanément tu as le bon résultat. Super ! Tu pousses en prod et tu vas te prendre un café de façon nonchalante.

Quelques jours plus tard, on revient vers toi et on te dit que le système est devenu super lent. C’est à cause de ta fonction. Le temps de process de ta fonction monte à plus de 15 secondes ! Elle bloque fréquemment tout le système pendant plusieurs secondes.

La panique ! Tu regardes les logs et tu te rends compte que l’input en question c’est devenu des chiffres énormes. Parfois, l’input passé en paramètre de ta fonction monte jusqu’à 1 milliard. Un autre développeur a dû intervenir. Ta fonction est remplacée et tout revient à la normale. Tu vas voir le code et tu vois ça.

def getSum(n):
    return n * (n + 1) / 2

Cette fonction résout le problème instantanément, même quand l’input est 1000 milliards. Tu demandes au développeur en question sur Slack et sa réponse te perd encore plus.

« Salut ! Ta solution avait une tendance linéaire O(n) sauf que l’input était énorme. J’ai trouvé une solution constante O(1). Peu importe l’input, ça sera rapide maintenant. »

Tu regardes ton écran et tu as une seule question qui t’obsède.

Comment ça marche ?

Reprenons nos deux snippets de code. Comme je te disais, la clef est d’évaluer le nombre d’opérations nécessaire que la machine va devoir faire pour résoudre ton problème. Avec ta solution, il y a beaucoup d’opérations.

def getSum(n):
    sum = 0  <-- une affectation

    for number in range(1, n + 1): <-- une addition + range
        sum += number <-- n additions + n affectations

    return sum

On va pas faire le calcul exact du nombre d’opérations parce qu’on s’en fout du nombre exact en fait. On veut la tendance du nombre d’opérations nécessaires selon les paramètres d’entrée. Ce qui devrait te sauter les yeux maintenant, c’est la boucle ligne 4-5.

Les opérations pour résoudre ton problème vont être multipliées par la grandeur de ton input. Ton ordre de magnitude est directement lié au nombre n en entrée de ta fonction. Ta fonction a donc une tendance linéaire de O(n).

L’input est de 1 milliard ? Ça sera 1 000 000 000 * opérations à faire pour la machine.

Ce n’est pas le cas de l’autre fonction.

def getSum(n):
    return n * (n + 1) / 2 <-- trois opérations

Avec cette solution, les opérations pour résoudre ton problème ne vont pas augmenter en même temps que ton input. Ton ordre de magnitude sera toujours de trois opérations, peu importe l’input. Ta fonction a donc une tendance constante de O(3), qu’on simplifie à O(1). Si on fait un dessin, ça ressemble à ça.

Tu commences à comprendre pourquoi c’est important d’avoir cette notion en tête ? Il existe évidemment d’autres cas de figure pour cette notation. Faisons un tour d’horizon rapide.

Big O notation par l’exemple

Complexité constante O(1)

La complexité constante O(1) ne change pas peut importe les paramètres d’entrée. Le même nombre d’opérations est nécessaire dans tous les cas.

def exempleO1(n):
    print(n + n)

Complexité logarithmique O(log(n))

La complexité logarithmique O(log(n)) est plus tricky à comprendre si t’as pas la notion de logarithme en math. De façon grandement simplifiée, une tendance logarithmique c’est l’opposé d’une tendance exponentielle. Là où une tendance exponentielle va se multiplier dans le temps, et les performances de ton algo avec, la tendance logarithmique va se diviser.

def exempleOlogn(n):
    i = 1

    while(i < n):
        i = i * 2
        print(i)

L’algorithme de recherche dichotomique (binary search) fonctionne avec cette tendance.

Complexité linéaire O(n)

La complexité linéaire O(n) évolue en lien direct avec la taille de l’input. Le nombre d’opérations grossit avec le nombre de l’input en entrée. L’exemple le plus simple c’est une simple boucle.

def exempleOn(n):
    for number in range(n):
            print(number + 1)

Complexité linéarithmique O(n log(n))

La complexité linéarithmique O(n log(n)) utilise la même approche « divide and conquer » que la complexité logarithmique sauf qu’elle le fait sur chaque élément de l’input n.

def exempleOlogn(n):
    i = 1
    for number in range(n):
        while(i < n):
            i = i * 2
            print(i)

L’algorithme de tri fusion (merge sort) fonctionne avec cette tendance.

Complexité quadratique O(n²)

La complexité quadratique O(n²) va évoluer au carré de l’input. Le nombre d’opérations grossit au carré de l’input en entrée. Deux boucles imbriquées c’est le parfait exemple pour cette tendance.

def exempleOn2(n):
    for number in range(n):
        for number in range(n):
            print(number + 1)

Les algorithmes de tri les plus connus (quick sort, bubble sort, insertion sort) ont cette tendance.

On a survolé les plus importants, mais y’en en a plein d’autres dont je te parle pas. Si tu veux tous les voir, la page wiki est intéressante.

Également, je te conseille cette courte vidéo YouTube qui est EXCELLENTE pour comprendre les règles de simplification d’écriture de la notation. Par exemple pourquoi O(3) est simplifié en O(1) ? Pourquoi deux boucles non imbriquées restent dans une complexité O(n) ? Comme n’importe quel sujet dans ton métier, y’a un océan de savoir.

Pour finir, on va discuter de pourquoi tout ceci est important.

Pourquoi c’est important ?

Je vois arriver les développeurs travaillant avec des petits volumes persuadés que tout ceci leur servira à rien. Ou même des développeurs avec 300 ans d’expérience et qui n’ont jamais eux besoin de tout ça.

La Big O notation répond rapidement à une question que tout développeur devrait se poser pendant son travail. À quel point ma solution scale ? Et peu importe si tes volumes sont énormes ou pas. C’est important que tu comprennes les limites de tes solutions pour estimer les limites de ton système.

Ensuite, en comprenant cette notion, tu vas avoir un langage standard pour discuter avec d’autres développeurs. C’est important pour comparer des solutions, faire des trade-off et simplement échanger techniquement. Si tu comprends pas de quoi on parle, tu pars avec un handicap. Personnellement, ça m’est même arrivé en entretien en début de carrière. J’avais aucune idée de quoi il parlait et j’étais en panique.

Le fait d’avoir cette compréhension de fond a changé la façon dont j’abordais ensuite les problèmes. Mes solutions n’ont jamais été aussi optimisées. Et en tant que développeur, c’est important de faire du code optimisé.

Enfin et surtout, ces notions vont te permettre de repérer rapidement ce qui ne va dans un système lent. On passe beaucoup de temps à lire et réparer du code d’autres développeurs. Tout ça va te permettre de trouver plus rapidement et optimiser des bouts de code lent.

Épilogue

J’espère que cette introduction à la notation Big O t’a donné envie d’en savoir plus. C’est important de connaitre ce concept pour mieux réfléchir à l’optimisation de son code. Et de façon générale, ça te sera de plus en plus utile et au fur et à mesure de l’évolution de ta carrière.