Я узнал: Вложенные циклы for/while могут иметь временную сложность O(N) в некоторых случаях (DSA для технических интервью)

Сложность по времени вложенного цикла в Python зависит от того, как структурированы циклы. Цикл while внутри цикла for может по-прежнему привести к сложности O(N) в определенных случаях. В первом примере цикл while выполняется только раз за итерацию цикла for и выполняет работу за константное время, что приводит к сложности O(N). Во втором примере цикл while работает за константное количество времени за каждую итерацию цикла for, снова приводя к сложности O(N). В третьем примере условие цикла while означает, что он будет увеличивать переменную только до N в общей сложности, что также приводит к сложности O(N). Ключевым выводом является то, что если количество итераций внутреннего цикла while не зависит от цикла for, то общая сложность может оставаться O(N). Сложность будет только O(N^2), если внутренний цикл while будет работать N раз за каждую итерацию внешнего цикла for. Примером сложности O(N^2) является случай, когда цикл while работает N раз за каждую итерацию цикла for. В этом случае цикл for работает N раз, а цикл while работает N раз за каждую итерацию цикла for, что приводит к сложности O(N^2). Структура вложенных циклов определяет общую сложность по времени.