Comprendre la complexité des boucles en code sans être un crack en maths

Cette vidéo explique comment déterminer la complexité temporelle de boucles imbriquées, une notion clé en informatique pour évaluer l'efficacité d'un algorithme.

L'idée principale est que la complexité d'une boucle simple est proportionnelle à son nombre d'itérations (noté n). Pour des boucles imbriquées, on multiplie généralement les complexités. Si deux boucles tournent toutes les deux n fois, la complexité totale est n × n, soit n². Cependant, il faut faire attention aux constantes : si la deuxième boucle ne tourne qu'un nombre fixe de fois (par exemple 100), cette valeur est considérée comme une constante et disparaît dans l'analyse asymptotique. La complexité reste alors linéaire, soit n, car la partie constante devient négligeable quand n est très grand.

Le cas le plus subtil concerne les boucles où la limite de la boucle interne dépend de la variable de la boucle externe. Ici, on ne peut pas simplement multiplier les bornes. Il faut compter le nombre total d'itérations réelles.