Журнал временной сложности генератора Python (n)

Question

В диапазоне python3, построенном с помощью генераторов

Логарифмическое время - O (log n) Говорят, что алгоритм имеет сложность логарифмического времени, когда он уменьшает размер входных данных на каждом шаге. Например, если мы печатаем первые 10 цифр с помощью генераторов, сначала мы получим один элемент, чтобы обработать оставшийся 9 элемент, затем второй элемент, чтобы обработать оставшийся 8 элемент

for index in range(0, len(data)):
    print(data[index])

Когда я проверяю URL путаница сложности времени генераторов питона его высказывание O (n).

Так как каждый раз, когда он генерирует только один вывод, потому что нам нужно сделать __next__, это будет каждый раз, когда стоимость одной единицы.

Могу ли я получить объяснение по этому поводу

Answer 1

Это объяснение логарифмической сложности времени неверно.

Вы получите логарифмическую сложность, если вы уменьшите размер входных данных на долю, а не на фиксированную величину. Например, бинарный поиск делит размер на 2 на каждой итерации, поэтому это O (log n). Если входной размер равен 8, то потребуется 4 итераций, удвоение размера до 16, только увеличение итераций до 5.