Почему n вызовов append дают линейное, а не квадратичное время
Список в CPython — динамический массив: элементы лежат в непрерывном буфере, и когда место заканчивается, append выделяет новый буфер и копирует туда всё накопленное содержимое.
out = []
for x in data: # n элементов
out.append(x)
Казалось бы, копирование внутри цикла обязано дать квадрат. Почему на самом деле весь цикл отрабатывает за O(n)?
- Копирования нет вовсе: список в CPython реализован как связный, и `append` просто цепляет новый узел к хвосту, не трогая уже добавленные элементы
- Копирование есть, но выполняется кодом на уровне C, а операции, реализованные в C, в асимптотику не входят: считаются только витки Python-цикла
- Интерпретатор заранее вычисляет длину `data` и выделяет буфер нужного размера ещё до начала цикла, поэтому расширений не происходит ни разу
- Буфер расширяется не на один элемент, а с запасом, пропорциональным текущему размеру: расширений выходит порядка log n, а суммарно копируется порядка n элементов — амортизированно O(1) на вызов