Почему операция добавления элементов в список (append) в Python выполняется за O(n), а не за O(n log n)?

Добрый день!

В Python операция добавления элемента в список с использованием метода `append()` выполняется в среднем за время O(1), а не O(n) или O(n log n). Это связано с тем, как работает динамический массив, который используется за кулисами для реализации списка.

### Как работает `append()` и динамический массив

1. **Динамическое управление памятью**: Когда вы создаете список в Python, выделяется определенный объем памяти под элементы списка. Если вы добавляете элементы и не превышаете этот объем, операция `append()` выполняется очень быстро — за O(1) — так как просто добавляется элемент в уже выделенную память.

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

3. **Увеличение емкости**: Однако, для улучшения производительности, новая емкость обычно устанавливается значительно больше, чем просто на один элемент. Обычно используется стратегия двойного увеличения: когда емкость списка достигает своего предела, она увеличивается примерно вдвое. Это означает, что перераспределение происходит реже, что приводит к тому, что в среднем время выполнения операции `append()` остается O(1).

### Как работает `list_resize`

В Python для масштабирования списка используется алгоритм `list_resize`. Вот краткое описание его работы:

- При каждом `append()` Python проверяет, достаточно ли места в текущем массиве для добавления нового элемента.
- Если мест нет, вызывается `list_resize`, которое выполняет следующие действия:
  - Выделяет новый массив с увеличенной емкостью (чаще всего в 1.125-1.5 раза больше, чем предыдущая емкость).
  - Копирует элементы из старого массива в новый.
  - Освобождает память, выделенную для старого массива.
- Размер нового массива выбирается так, чтобы уменьшить вероятность частых перераспределений и повысить общую производительность.

### Заключение

Таким образом, несмотря на то, что операция `append()` может занимать O(n) при перераспределении, частота этих перераспределений очень мала, и в среднем на `append` получается O(1) благодаря стратегии увеличения емкости списка. Поэтому `append()` реализуется эффективно для большинства случаев, что делает списки в Python удобными и быстрыми для использования.

Потому что, здесь вступает в игру такое понятие как амортизированная сложность. Для динамических массивов, которые увеличиваются в несколько раз (т.е. не + 10, а *2 например), амортизированная сложность - O(1). 
 Поэтому, у тебя O(n) * O(1) = O(n) (амортизированное)

а общее число перераспределений для n добавлений уменьшается как O(logn).  Почему тогда в таком случае для n последовательности append-ов общая сложность равна O(n), а не O(n logn)? 
 
 
 Потому что эти распределения разного размера. Первое - совсем маленькое. Второе чуть больше и т.д. Чтобы суммарно было O(n Log n), каждое из них должно быть пропорционально n. 
 
 
1+4+10+⋯≤O(n)
 
 
 Вот это и есть ответ. Первые слагаемые маленькие. Получается геометрическая прогрессия, которая дает линейную сумму от n.