J'ai appris aujourd'hui (TIL) : Les boucles for/while imbriquées peuvent avoir une complexité temporelle de O(N) dans certains cas (DSA pour les entretiens techniques)

La complexité temporelle d'une boucle imbriquée en Python dépend de la façon dont les boucles sont structurées. Une boucle while à l'intérieur d'une boucle for peut encore résulter en une complexité de O(N) dans certains cas. Dans le premier exemple, la boucle while s'exécute uniquement une fois par itération de la boucle for et effectue un travail en temps constant, résultant en une complexité de O(N). Dans le deuxième exemple, la boucle while s'exécute un nombre constant de fois pour chaque itération de la boucle for, résultant à nouveau en une complexité de O(N). Dans le troisième exemple, la condition de la boucle while signifie qu'elle ne fera que incrémenter une variable jusqu'à N au total, résultant en une complexité de O(N). La principale conclusion à tirer est que si le nombre d'itérations de la boucle while interne est indépendant de la boucle for, la complexité combinée peut rester O(N). La complexité ne serait que O(N^2) si la boucle while interne s'exécutait N fois pour chaque itération de la boucle for externe. Un exemple de complexité O(N^2) est lorsque la boucle while s'exécute N fois pour chaque itération de la boucle for. Dans ce cas, la boucle for s'exécute N fois et la boucle while s'exécute N fois pour chaque itération de la boucle for, résultant en une complexité de O(N^2). La structure des boucles imbriquées détermine la complexité temporelle globale.