Que ayez eu un prof à l’ancienne durant vos études, où que vous vous soyez plongé dans des documents traitant d’optimisation, vous êtes peut être un jour tombé sur ces fameuses notations : O(n), O(1), O(log(n)), etc.
Qu’est-ce que cela signifie-t-il donc, alors, hein ?
C’est une manière de décrire l’ordre de grandeur de temps que va prendre un algo pour s’exécuter pour un nombre “n” d’éléments.
Par exemple, si je fais ceci en Python :
elements = [1, 2, 3] for x in elements: print(x) ## 1 ## 2 ## 3 |
Ici, j’ai 3 éléments, donc n = 3. Mon algorithme va tous les utiliser une fois, mais pas plus d’une. Il va donc faire un nombre d’opérations proportionnel au nombres d’éléments. On note ce type de comportement O(n). Cela signifie que le temps de traitement de mon code suit à peu près “n”.
Je dis à peu près car le nombre d’éléments n’est pas uniquement ce qui va rentrer en compte. La taille des éléments, l’état de la machine au moment de l’exécution et tout un tas d’autres paramètres vont être des facteurs. Mais, globalement, je peux donner une évaluation convenable du temps que le code va prendre en notant le temps de traitement d’un seul élément, et en le multipliant par le nombre total d’éléments.
La notation O(truc), que l’on prononce “Oh de truc”, sert juste à indiquer quel type de comportement un algo a : est-ce qu’il prend du temps par rapport au nombre d’éléments ? Si oui à quel point ?
“A quel point” est une question importante, car si mon algo est celui ci:
elements = [1, 2, 3] for x in elements: print() for i in elements: print(i, end="") ## 123 ## 123 ## 123 |
Alors, si n est grand, non seulement ma première boucle s’allonge, mais ma seconde boucle s’allonge aussi car j’affiche TOUS les éléments pour CHAQUE élément. Mon temps d’exécution dépend alors de “n” multiplié par lui-même : n X n. En effet, si j’ai 2 éléments, je vais faire 2 x 2 = 4 print(), si j’en ai 3, je vais faire 3 x 3 print(), etc.
Bien sûr, je pourrais faire des choses beaucoup plus compliquées qu’un print(), mais ça n’a pas d’importance. On en mesure pas le temps de tout le programme, seulement l’efficacité d’un algorithme. Ici, cela dépend du nombre d’éléments fois lui-même, soit au carré. On le note O(n²).
Il existe tout un tas de ces notations. Par exemple, 0(1) signifie un temps “constant”, c’est un abus de langage pour dire que le temps que met l’ago à s’effectuer ne dépend pas du nombre d’éléments.
Par exemple :
elements = [1, 2, 3] print(elements[0]) ## 1 |
Afficher le premier élément prend un temps du même ordre de grandeur – car c’est ça l’important, l’ordre de grandeur – si il y a 1 ou 10000 éléments. On note donc cet algo O(1).
Il y a des cas plus complexes. Imaginez celui-ci :
import random number = random.randint(0, 100) print("Choosing: %s" % number) smallest = 0 biggest = 100 guess = 50 while guess != number: if number >= guess: smallest = guess else: biggest = guess guess = (biggest - smallest)//2 + smallest print("New guess: %s" % guess) print("Last guess: %s" % guess) ## Choosing: 69 ## New guess: 75 ## New guess: 62 ## New guess: 68 ## New guess: 71 ## New guess: 69 ## Last guess: 69 |
Dans cet exemple, le nombre d’opérations dépend du nombre d’éléments “n” (ici 100) mais on divise l’interval de recherche par deux à chaque tour de boucle. On note cette complexité O(log n), puisque la fonction log illustre bien le concept d’avoir une mi-molle sur la fin de son algo :)
Il y a aussi l’inverse :
elements = [1, 2, 3, 4, 5] copies = [] for x in elements: print() for i in copies: print(i, end="") copies.extend(elements) ## 12345 ## 1234512345 ## 123451234512345 ## 12345123451234512345 |
Ici on augment la charge à traiter à chaque tour de boucle, et cette augmentation dépend du nombre d’éléments “n”. On parle d’une augmentation exponentielle de la charge de travail et on le note O(en).
A quoi ça sert ?
Essentiellement à avoir une idée d’où on met les pieds. Si vous lisez une doc, et qu’on vous dis “cet algo met un temps O(log(n))”, vous savez que même sur un grand ensemble de données, le traitement ne sera pas trop agressif. Si plus tard vous rencontrez des problèmes de perf, ce ne sera pas le premier endroit à regarder.
Par contre si vous lisez qu’un algo est O(n!) – là on tape dans les factoriels, c’est énorme – alors au premier ralentissement il faut jeter un coup d’œil sur ce bout de code.
C’est aussi utile pour comparer l’efficacité de deux implémentations.
Imaginez la structure suivante :
class Examen: """C'est un exemple pédagogique, ne faites pas ça chez vous les enfants""" def __init__(self): self.notes = [] def ajouterNote(self, note): self.notes.append(note) def moyenne(self): total = 0 for note in self.notes: total += note return total / len(self.notes) |
Récupérer la moyenne est une opération O(n). En revanche, si on a :
class Examen: def __init__(self): self.notes = [] self.moyenne = None def ajouterNote(self, note): if self.moyenne is None: self.moyenne = note else: self.moyenne = (len(self.notes)*self.moyenne + note) / (len(self.notes)+1) self.notes.append(note) |
Là, récupérer la moyenne devient une opération O(1), on a déchargé et réparti le calcul sur l’ajout des notes. Selon que l’application va lire souvent la moyenne ou non, l’un ou l’autre algo est préférable, et la notation Big O va donner une idée duquel utiliser si on est face à la doc et pas au code, qui est généralement vachement plus compliqué que ça.
Bon, ok, dans la VVV, aucune de ces deux solutions n’est un problème, on s’en branle. Mais sur des algos plus riches, sur du matos plus limité, ou un jeu de données plus grand, c’est important. Ainsi, la doc de redis donne la notation Big O de toutes les commandes.
En Python, qui est quoi ?
Parcourir un itérable, c’est généralement du O(n), en tout cas pour les listes, les tuples, les dicos, les strings et les sets. Ajouter un élément ou en retirer un, c’est du O(1). Récupérer leurs tailles, c’est du O(1) aussi (elle est mise en cache), donc vous pouvez y aller avec len().
En revanche, l’opérateur in a un temps moyen de O(n) pour les strings, les tuples et les listes (il doit parcourir l’itérable jusqu’à trouver l’élément), et un temps de O(1) pour les sets et les dicos. Ces derniers utilisent des hash, rendant la recherche très très rapide. C’est pour cela qu’on vous dit d’utiliser la bonne structure de données pour le bon usage.
Attention cependant, c’est de l’optimisation de poil de cul, mais c’est pour la culture, O(1) ne veut pas dire “plus rapide que O(n)”. O(1) veut juste dire que le temps est indépendant du nombre d’éléments. Ainsi :
1 in [1, 2, 3] sera beaucoup plus rapide que 1 in [1, 2, 3..., 1000].
Et :
1 in {1, 2, 3} prendra un temps similaire à 1 in {1, 2, 3..., 1000}
Mais :
1 in {1, 2, 3} peut tout à faire être plus lent que 1 in [1, 2, 3]
Par contre, il est presque certain que :
1 in {1, 2, 3..., 1000} est BEAUCOUP plus rapide que 1 in [1, 2, 3..., 1000]
De plus, il y énormément de structures de données dans la stdlib Python, toutes avec des capacités différentes. Heapq assure que votre structure de données est toujours ordonnées pour un coût de O(log n) à l’insertion. Les deques sont très rapides comme FIFO/LIFO (O(1)), mais récupérer une donnée au milieu est une opération O(n). Certaines opérations, comme retirer un élément d’un type list sont étonnamment coûteuses ((O(n) dans le cas du del).
Voici quelques notations de la doc de Python.
La théorie, la pratique, et la mauvaise foi
La notation O est une bonne indication pour faire un choix d’algo ou pour commencer ses recherches de goulot d’étranglement dans un code.
Néanmoins, c’est la performance sur la papier. En pratique, on peut obtenir des résultats un peu différents, voir carrément surprenant. Il peut y avoir de multiples causes :
- L’implémentation ne se comporte pas comme prévu. CPython et Jython n’ont pas les mêmes perfs pour les mêmes choses. Jython n’a pas de GIL.
- Vous avez oublié un paramètre. Un accès disque ou un accès réseau au mauvais endroit, et bam, votre évaluation est à revoir.
- Les données de la vie réelle ont généralement des tendances. Par exemple elles sont souvent un peu triées plutôt que complètement en bordel. C’est pour cette raison que Python utilise Timsort.
- Le matos ne fait pas ce que vous croyez. Les processeurs / cartes graphiques actuels sont devenus incroyablement efficaces à certaines opérations réputées lentes
- Votre machine ne fait pas que faire tourner votre algo. Il y a d’autres processus, avec des conséquences.
Donc si les perfs sont importantes, comme toujours en informatique, on a le dernier mot en mesurant soi-même.
“Je dis à peu prêt car”… je ne sais pas écrire “à peu près”, peut-être ? :-)
Juste pour dire que ce n’est pas un abus O(1) désigne l’ensemble des suites (dans le cas général des fonctions) qui sont majorées. Ainsi un algo qui prend 300 calculs au pire (quelle que soit la donnée au départ) est bien un O(1):
le nombre de calculs pour une donnée de taille 1 est U_1 et est inférieure à 300
le nombre de calculs pour une donnée de taille 2 est U_2 et est inférieure à 300
le nombre de calculs pour une donnée de taille 3 est U_3 et est inférieure à 300
le nombre de calculs pour une donnée de taille 4 est U_4 et est inférieure à 300
le nombre de calculs pour une donnée de taille n est U_n et est inférieure à 300.
Pour les classes examen je crois voir un “x” là où il devrait y avoir une “note”. Et puis même si ce n’est qu’un exemple la seconde class examen rend la dernière note toujours plus importante par rapport à la première. La moyenne ne sera pas du tout la même pour les deux classes (ou je me trompe ?).
avec
self.moyenne=(len(self.notes)*self.moyenne+note)/(len(self.notes)+1)suivi de
self.notes.append(note)ça devrait marcher comme le précédent.@raph: :)
@yauk: ce qui est l’abus c’est le “temps constant”. Car le temps n’est pas vraiment constant. L’ordre de grandeur l’est. Et tu as tout à fait raison, mon second calcul est complètement foireux.
J’ai fais les corrections. Une preuve de plus qu’il ne faut jamais me laisser faire des maths sans la supervision d’une personne majeure et d’un baudrier.
Celui avec pop() utilise n*(n-1)/2 opérations. Donc en O(n^2).
Damn it. Il faut que je change d’exemple.
Je ne suis pas sur que ton premier exemple de O(n log n) soit juste. Cet exemple est plutôt un 0(n*n/2), d’ailleurs tu imprimes un triangle qui est la moitié d’un carré de n de côté.
Un exemple similaire pour 0(n log n) serait de diviser “copies” par 2 à chaque itération de la première boucle à la place de faire un pop.
Le code annoncé en O(n log n) est en fait en O(n**2) car il fait n*(n+1)/2 print(i) (+n print()).
Un code en O(n log n) sera plutôt du type:
car il y a O(log x) nombres du type 2**y plus petit que x pour chaque x.
Bon, je vais prendre le bon vieil exemple de deviner un nombre. On ne change pas une équipe qui gagne.
Exemple de n log n corrigé.
Bon, là, j’ai à dire :)
Déjà O(n/2), ça n’existe pas. C’est O(n).
La notation en O(truc) ne sert pas à comparer quel algorithme est plus rapide que l’autre mais de voir comment évolue le temps de traitement en fonction du nombre d’éléments à traiter.
Certes, si je parcours une liste pour en trouver un élément, parfois l’élément est au début et parfois à la fin et, en moyenne, on parcours que la moitié de la liste. Mais c’est pas le problème. Le truc c’est que si je double la taille de la liste, je double le nombre de tests d’égalité. Peu importe que je parcours que la moitié de la liste. Je fais toujours deux fois plus de tests en moyenne qu’avant.
Donc c’est du O(n).
Et si quand je double la taille du conteneur, je quadruple mon temps alors c’est du O(n**2)
Il faut comprendre :
Si mon temps de traitement pour n élément est t alors pour n’=2*n éléments on a
t’ = O(n’*n’) = O(2n*2n) = 4*O(n*n) = 4*t
Enfin, pour CPython, la list est implémentée avec un tableau. C’est certes utile pour accéder a un élément O(1), mais le temps d’insertion est en O(n), pas en O(1).
Et le petit lien qui va bien https://wiki.python.org/moin/TimeComplexity :)
Le lien que j’ai donné est déjà dans ton article. Ça m’apprendra à pas cliquer sur tous les liens que tu donnes :)
La rédaction de cet article a une complexité de O(n), avec n étant le nombre de commentaire qui corrige mes bêtises.
Nan, c’est du O(log(n)) parce que plus le temps passe, plus les commentaires relèvent les mêmes erreurs !
On a parle d’une augmentation exponentielle de la charge de travail et on le note O(ex).
dervait plutôt être :
On
aparle d’une augmentation exponentielle de la charge de travail et on le note O(en).J’ai beaucoup de mal avec la structure de cette phrase :
Certaines opérations, comme retirer un élément d’un type list (O(n)) sont étonnamment coûteuses.
Le “(O(n))” me semble mal placé (mais c’est peut être dû à mes neurones).
Et j’ai cherché mais j’ai rien trouvé d’intelligent à ajouter dans mon commentaire.
A pars peut être que de bons exemples sur ce genre de notation sont dispo avec les algorithmes de tri.
Exemples visuels (j’en avais un meilleur mais impossible de remettre la main dessus) et une “petite” cheatsheet
Ouai, je vais déplacer les parenthèses à la fin, ça sera plus clair.
Intéréssant tout ca.
Par contre si tu as quelque chose dans ce genre :
pour i jusqu'a 10
pour j jusqu'a 15
pour k jusqu'a 2
afficher "Coucou cuicui, c'est moi super connard."
finpour
finpour
finpour
Tu as un O(n^3) ou bien O(n*m*p) ?
O(n * m * p) si les variables sont d’ordre de grandeur différentes, O(n^3) si elles sont de même ordre de grandeur.
Plutôt qu’un ordre de grandeur, je dirais plutôt si elles sont liées. Plus précisément, O(m*n*p) == O(n^3) si m, n et p sont proportionnels.
Donc dans l’exemple que j’ai mis plus haut, avec i,j,k=0, nous aurions O(m*n*p), c’est bien ça ?
En revanche si nous avions “jusqu’à 10″ pour chaque boucle, nous aurions O(n^3).
Disons plutôt si jusqu’à x était un facteur de jusqu’à z qui était un facteur de jusqu’à y, tu aurais O(n^3).
Il y a un très bon MOOC sur les algo et qui reprend les notions de complexité. Il y a des TPs vraiment prise de chou … mais c’est super enrichissant. Pas en python mais en java, mais rien n’empêche après de les refaire en python ;)
https://www.coursera.org/course/algoprog
(j’ai chié mon lien désolé …)
Ajouter ou retirer un élément a une position quelconque d’une liste est en O(n). C’est seulement si l’élément est vers la fin que ces accès sont en O(1).
donc
l=list(range(0,1000))
l.insert(99,0) # O(n)
x=l.pop(0) # O(n)
#mais
l.append(98) # O(1)
x=l.pop() # O(1)
Attention avec vos exemples: à partir du moment où votre nombre d’élément est fixé, on ne peut plus parler de complexité algorithmique, puisque plus rien ne peut varier: on sera alors toujours en temps constant: si n=100, O(n) == O(100) == O(1).
L’exemple de Xavier serait par exemple:
Pour Oyabi, on aurait plutôt ça en O(n*m*p):
et ça en O(n**3):