La Notation Big O Expliquée avec des Exemples de Code
Une recherche dans un dictionnaire Python prend environ 100 nanosecondes, que le dictionnaire contienne 1 000 clés ou 1 000 000. Une double boucle qui cherche des doublons dans une liste prend une demi-milliseconde sur 200 éléments et 136 millisecondes sur 3 200. Seize fois l’entrée, presque 280 fois l’attente. Même machine, même Python. La notation Big O est le nom de cette différence. Ce que mesure la notation Big O Big O décrit comment le temps d’exécution (ou l’utilisation de la mémoire) d’un morceau de code croît quand l’entrée grandit. Ce n’est pas une mesure au chronomètre, et peu importe que votre ordinateur soit rapide ou lent. Ce qui compte, c’est la forme de la courbe de croissance : quand vous doublez l’entrée, le temps double-t-il, quadruple-t-il, ou bouge-t-il à peine ? ...