Динамический массив: почему append работает за O(1)

Коротко

Список в Python и массив в JavaScript — это динамические массивы. Понимание их устройства объясняет, почему одни операции дешёвые, а другие внезапно дорогие.

Проблема обычного массива

Классический массив занимает непрерывный кусок памяти фиксированного размера. Это даёт мгновенный доступ по индексу: адрес элемента вычисляется как начало + индекс × размер элемента, одна арифметическая операция.

Но размер задан заранее. Как добавить 101-й элемент в массив на 100 ячеек? Соседняя память может быть занята другими данными.

Единственный способ — выделить новый блок побольше и скопировать туда всё старое. Копирование стоит O(n).

Наивное решение и почему оно плохое

Допустим, при каждом добавлении мы увеличиваем массив ровно на одну ячейку. Тогда добавление n элементов обойдётся в

1 + 2 + 3 + ... + n = n(n+1)/2 ≈ n²/2 операций копирования

Заполнение списка миллионом элементов потребует порядка 5·10¹¹ операций. Неприемлемо.

Решение: удваиваем ёмкость

Ключевая идея — при нехватке места выделять вдвое больше, а не на одну ячейку.

ёмкость 1  →  заполнили  →  копируем 1 элемент,  ёмкость 2
ёмкость 2  →  заполнили  →  копируем 2 элемента, ёмкость 4
ёмкость 4  →  заполнили  →  копируем 4 элемента, ёмкость 8
ёмкость 8  →  заполнили  →  копируем 8 элементов, ёмкость 16

Посчитаем общее число копирований при добавлении n элементов:

1 + 2 + 4 + 8 + ... + n < 2n

Это сумма геометрической прогрессии, и она меньше 2n. То есть на n добавлений приходится меньше 2n операций копирования — в среднем меньше двух на элемент. Это и есть O(1) амортизированно.

Что такое амортизированная сложность

Отдельное добавление может стоить O(n) — если именно на нём случилось расширение. Но такие дорогие операции происходят редко и «оплачиваются» множеством дешёвых.

Аналогия: вы платите за годовой абонемент в спортзал разом. В день покупки расход большой, но если размазать по году, выходит немного в день. Амортизированный анализ считает именно среднюю стоимость в длинной последовательности операций, а не худший случай отдельной.

Важно не путать со средним случаем: амортизированная оценка — это гарантия для любой последовательности операций, а не вероятностное утверждение.

Реализация на Python

class DynamicArray:
    def __init__(self) -> None:
        self._capacity = 1
        self._size = 0
        self._data = [None] * self._capacity

    def __len__(self) -> int:
        return self._size

    def __getitem__(self, index: int):
        if not 0 <= index < self._size:
            raise IndexError('индекс вне диапазона')
        return self._data[index]

    def append(self, value) -> None:
        if self._size == self._capacity:
            self._resize(self._capacity * 2)   # вот здесь O(n)
        self._data[self._size] = value
        self._size += 1

    def _resize(self, new_capacity: int) -> None:
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_capacity


arr = DynamicArray()
for i in range(10):
    arr.append(i)
print(len(arr), arr[5])   # 10 5

Почему именно вдвое

Коэффициент роста — компромисс между памятью и скоростью.

Слишком маленький (например, ×1.1) — расширения происходят часто, копирований много.

Слишком большой (например, ×10) — расширений мало, но память тратится впустую: массив из 101 элемента займёт место под 1000.

Двойка даёт разумный баланс и удобна тем, что операция дешёвая на уровне процессора. На практике реализации отличаются:

• CPython для списков использует коэффициент около 1.125 плюс небольшая добавка — экономит память ценой более частых расширений;
• C++ std::vector в GCC удваивает;
• Java ArrayList растёт в 1.5 раза.

Коэффициент меньше 2 имеет неочевидное преимущество: освобождённые блоки могут переиспользоваться аллокатором, потому что сумма всех предыдущих блоков превышает следующий запрос.

Что из этого следует на практике

Добавление в конец дёшево, вставка в начало — нет. list.insert(0, x) сдвигает все элементы: O(n). Если нужно часто добавлять в начало, берите collections.deque.

from collections import deque

d = deque()
d.appendleft(1)   # O(1), в отличие от list.insert(0, 1)

Заранее известный размер лучше выделить сразу. Если вы знаете, что будет миллион элементов, создание [None] * 1_000_000 избавит от двадцати расширений.

Удаление из середины тоже O(n). list.pop(0) сдвигает весь хвост. list.pop() без аргумента снимает с конца за O(1).

Память не возвращается сразу. После удаления элементов ёмкость обычно не уменьшается — массив остаётся большим. Некоторые реализации сжимают его, когда заполненность падает ниже четверти. Порог именно 1/4, а не 1/2, чтобы избежать «дрожания»: при пороге в половину чередование добавления и удаления на границе вызывало бы расширение и сжатие на каждой операции.

Сравнение со связным списком

Последняя строка часто перевешивает теорию. Элементы массива лежат подряд, и процессор подгружает их в кеш целыми блоками. Связный список разбросан по памяти, и каждый переход по указателю может стоить обращения к оперативной памяти. Поэтому на практике массив выигрывает даже там, где асимптотика обещает обратное.

Частые ошибки

Расчёт на O(1) для insert(0, x). Самая распространённая. Цикл с вставкой в начало на 100 000 элементов превращается в 5 миллиардов операций.

Удаление во время итерации. Индексы сдвигаются, и часть элементов пропускается. Итерируйте по копии или собирайте новый список.

Проверка размера через capacity вместо size. В собственной реализации это даст доступ к неинициализированным ячейкам.

Что запомнить

• Динамический массив хранит данные непрерывно и удваивает ёмкость при нехватке места.
• Удвоение даёт амортизированную O(1) на добавление: сумма копирований меньше 2n.
• Амортизированная сложность — гарантия для последовательности операций, а не средний случай.
• Вставка и удаление в начале и середине стоят O(n).
• Непрерывность памяти даёт отличную работу с кешем — часто это важнее асимптотики.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→