Какая алгоритмическая сложность перебора списка

Перебор списка в Python имеет линейную временную сложность O(n), где n — количество элементов в списке. Это связано с тем, что каждый элемент посещается ровно один раз.

Пример:

my_list = [1, 2, 3, 4, 5]
for item in my_list:  # O(n)
    print(item)

Если внутри цикла выполняются операции с постоянной сложностью O(1), общая сложность остаётся O(n). Однако если внутри цикла есть вложенные операции с более высокой сложностью, общая сложность увеличивается.

Важно: доступ по индексу в списках Python — O(1), так как списки реализованы как динамические массивы.