Leçon 4 : Big-O et analyse de complexité

Imagine un énorme annuaire téléphonique et tu cherches un nom : feuilleter page par page prend une éternité, mais un annuaire classé par ordre alphabétique offre une bien meilleure approche. Cette leçon donne un nom court à ce genre de schéma — le Big-O — une façon pratique de décrire comment le tra

Le Big-O, c'est simplement se demander : « si tu doubles le nombre d'éléments, combien de travail en plus ça représente ? ». Si tu parcours chaque élément une fois, doubler les éléments = doubler le travail (on appelle ça O(n)). Si tu compares chaque élément à chaque élément, doubler les éléments = quatre fois plus de travail (O(n²)). Voilà — un nom court pour la vitesse à laquelle le travail grandit.

analyse de complexité: Estimer le travail (temps) et la mémoire dont un algorithme a besoin en fonction de la taille de l'entrée n.
Big-O: Notation pour le taux de croissance dans le pire des cas d'un algorithme, en ignorant les constantes et les termes d'ordre inférieur.
temps linéaire: O(n) : le travail grandit proportionnellement à la taille de l'entrée — un passage sur chaque élément.