La notation Big O de Polo et sa troupe

En général il existe plusieurs manières de répondre à un problème en programmation. Mais ça revient plus ou moins au même … pas toujours pardi !

Sur peu de données, ça n’a pas d’importance. En général. En revanche avec moult données c’est plus la même histoire. C’est pour ça qu’un certain Paul et des potos ont créé la notation Big O, comme on dit de l’autre côté de la manche.

C’est une notion importante mais il n’y a pas besoin d’en connaître toutes les subtilités dans le cadre de la data science.

Big O est en fait une mesure pour savoir combien de temps ou d’espace prendra la machine pour faire quelque chose avec un algorithme. On s’intéresse surtout à la mesure en temps.

Grâce à ça, la puissance de la machine n’entre pas en ligne de compte. Donc que la personne ait une bonne machine ou non, qu’elle utilise tel ou tel langage de programmation … on s’en moque !

La question ne se pose pas en général parce que les calculs à effectuer sont relativement simples. On ne note pas de différence flagrante entre deux algos. Mais si on joue avec énormément de données alors la différence ne sera plus de l’ordre de la seconde mais de l’année. C’est ce que nous renseigne la notation Big O.

En ayant cette notation pour un algo, vous saurez comment celui-ci se comportera avec davantage de données. Combien de temps sera nécessaire.

Pour ce faire, on apporte une attention toute particulière à la bouff’ qu’on donne à notre algo ainsi qu’aux étapes qui le composent.

Concrètement

Quand j’ai une affectation, par exemple :

sum = 30 + 1

Le temps nécessaire pour réaliser cette opération ne dépend pas d’un paramètre d’entrée. J’ai une addition entre deux constantes. On peut traduire ça par = a + b

Donc quel que soit le paramètre d’entrée, le temps requis pour exécuter cette instruction sera identique ou constant :

Le nombre d’éléments en abscisse et le temps (s) en ordonnée

On parle de temps constant O(1)

Maintenant si j’ajoute une boucle pour répéter mon opération d’affectation :

for i in l:
    sum = 30 + 1

La ligne 2 s’exécute toujours en temps constant mais la boucle dépend de la taille de l. Donc on va exécuter autant de fois la ligne 2 qu’il y a d’éléments dans la liste l.

On dit que n représente la taille de la liste l. Ce qui nous donne = n*a+b. On cherche le terme le plus gros terme, à savoir n*a parce que les constantes ne valent plus grand chose si on augmente n.

On passe sur un temps linéaire : n fois O(1) donc O(n).

Le nombre d’éléments n’a pas d’importance. Ce qui nous intéresse c’est le fait de multiplier le temps proportionnellement au nombre d’éléments dans la liste :

Le nombre d’éléments en abscisse et le temps (s) en ordonnée

En revanche, enchaîne les instructions contantes ne me fera pas passer sur un temps linéaire :

sum = 30 + 1
add = 3 * 8
cal = 1 + 1 + 1 + 1 + 1 / 2

Lorsqu’on commence à avoir quelques lignes d’instructions, on calculera le temps pour chaque ligne et on prend le max, en respectant l’ordre :

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ) < O(n!)

Par exemple pour :

sum = 30 + 1 // O(1)
add = 3 * 8 // O(1)
cal = 1 + 1 + 1 + 1 + 1 / 2 // O(1)
for i in l: // O(n)
    sum = 30 + 1
for i in l: // O(n²)
    for j in n:
        sum = 30 + 1

Le terme le plus haut est O(n²).

On raisonne en général dans le pire des cas. Mais on peut très bien réfléchir au meilleur des des cas ou en moyenne (se référer à la hiérarchie des ordres de grandeur).

Grosso modo

La notation big O est une manière de formaliser mathématiquement « c’est constant« , « c’est linéaire« , « l’algo risque de prendre beaucoup trop de temps« , etc.

Il y a la notation O(1) pour un algo qui s’exécute en temps constant.

La notation O(n) pour un algo avec un temps d’exécution linéaire. Ça veut dire que si n augmente, le temps augmentera aussi ça la même cadence.

La notation O(n^2) pour un algo en temps d’exécution quadratique.

La notation O(log n) pour un algo en temps d’exécution logarithmique.

Source : bigocheatsheet