Devenir un meilleur développeur et prendre le contrôle de sa carrière

La boutique officielle est disponible !

6 juillet 2020 In algorithme comprendre développement développeur développeuse technique

, , , , ,

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.

Selon ta machine et tes processeurs

Selon le langage que tu utilises
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.

Tags: bigo , complexité algorithmique , développement , développeur , développeuse

Share

Previous post Next post

Comprendre Git en 7 minutes Comprendre les structures de données linéaires en 10

minutes

Qui me parle ?

Je suis un dev. En ce moment, je suis développeur backend senior / DevOps à Montréal pour
un géant du jeux vidéo. Le dev est l'une de mes passions et j'écris comme je parle. Je continue
à te parler quotidiennement sur mon Twitter Tu peux m'insulter à cet e-mail ou le faire .

directement dans les commentaires juste en dessous. Y'a même une newsletter !

Pour me soutenir, la boutique officielle est disponible Sinon désactiver le bloqueur de pub !

et/ou utiliser les liens affiliés dans les articles, ça m'aide aussi.

8 commentaires sur “Comprendre la notation Big O en 7 minutes”

Cam
6 juillet 2020 à 8 h 46 min

Hey, encore un excellent article C’était la découverte de mon WE, ton sujet tombe à pic. Un
!

grand merci & hâte de lire tes prochaines productions !

Répondre

ttoine
6 juillet 2020 à 10 h 54 min

Et c’est là qu’être bon en suite genre 1+n etc. est très important, finalement. Ce qui n’était pas
mon cas en math au lycée puis pendant mes études (une vraie frustration, les profs de math que
j’ai eu n’ont pas du tout aidé), et ça m’a poussé à ne pas devenir développeur, du coup.

Répondre

Grunk
6 juillet 2020 à 13 h 37 min

J’ai toujours été une monumentale bite en math et ca m’a pas empêcher de devenir ,

développeur. Ça fait pas de moi un mauvais dév (enfin j’espère :D) C’est mythe qu’il faut être .

bon en math pour être dév. Il faut être bon en logique surtout. Le niveau de math nécessaire
dépend beaucoup du domaine où on travail. En 15 ans j’ai pas du avoir plus de 2 ou 3 fois un
moment de solitude sur mon niveau de math.
Répondre

Vana
6 juillet 2020 à 16 h 50 min

Comme tu le dis, ça dépend du domaine, « être dev » ça veut tout et rien dire. Si ton quotidien
c’est faire du front t’as peu de chances de devoir faire des math, si ton quotidien c’est pas dealer
avec des opérations coûteuses et critique, t’as peu de chance de devoir réfléchir à la complexité
de tes algos ou a leur correction.

Par contre le problème c’est quand t’en a besoin et que tu sais pas ce que c’est où que tu t’en
fiche !

Répondre

FuckThePolice?
6 juillet 2020 à 23 h 41 min

« mais on s’en carre le cul du langage » belle formule, je la garde pour mes prochaines specs.
Répondre

maxime
9 juillet 2020 à 13 h 36 min

Question: Existe-t-il des solutions qui, pour du code en entrée, renvoie les parties de ce code dont
le score big O est « haut » ? Ca serait excellent un plugin dans ce genre là sur VS Code qui affiche
les bouts de code dont le Big O est supérieur à une valeur de référence choisie par l’utilisateur,
par exemple O(nlog(n)).
Répondre

HLEET
10 juillet 2020 à 21 h 52 min

Super article, j’adore lire tes posts, ils sont instructifs avec un brin d’humour très appréciable.
Merci pour ces explications de ce BIG O que je n’ai jamais osé comprendre d’avantage … moi et
les maths, on est pas très copains XD mais ça va au final, c’est digeste quand c’est expliqué
;

simplement.
Bonne continuation pour tes articles, tu déchires mec
Répondre

Samuel
10 avril 2024 à 15 h 03 min

Merci beaucoup pour cette superbe présentation qui ma permis de mieux comprendre moi qui
débute dans le grand océan de programmation.
Répondre

T'en penses quoi ?