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

Коротко

Динамический массив удваивает буфер, когда заполнен, и копирует всё старое. Возьмём потенциал Φ = 2·num − size (num - занято, size - ёмкость). При обычной вставке Φ растёт на 2, амортизированная цена 1 + 2 = 3. При вставке с удвоением дорогое копирование гасится ПАДЕНИЕМ Φ, и цена снова выходит 3. Значит вставка амортизированно O(1), хотя отдельная бывает Θ(n). Удвоение тут принципиально: расти на константу - и вставка стала бы Θ(n).

Если умеешь доказать амортизированное O(1) вставки в динамический массив потенциалом Φ=2·num−size, листай до «Теперь сам».

Как думаешь, во что обходится заполнение массива

num - сколько элементов лежит, size - на сколько хватает буфера. Пока num < size, вставка кладёт элемент за O(1). Когда num = size, места нет: заводим буфер вдвое больше, копируем все num элементов, потом вставляем - это Θ(num). Отношение num/size называют коэффициентом заполнения. Вопрос: если таких удвоений на длинной серии мало, во что обходится ОДНА вставка в среднем по серии? Докажем это методом потенциалов, а не агрегатно.

На что это похоже

Φ = 2·num − size - это счётчик «насколько массив заполнен СВЕРХ половины». Сразу после удвоения массив полупустой (num ≈ size/2), запас Φ мал. По мере заполнения num растёт, Φ копится - и к моменту, когда массив снова полон, запаса ровно столько, чтобы оплатить копирование при следующем удвоении. Как пружина: сжимаешь её дешёвыми вставками, а на удвоении она распрямляется и толкает копирование даром.

Механизм: считаем амортизированную цену

Потенциал Φ = 2·num − size. Проверим условия: на пустом массиве num = size = 0, Φ = 0; пока массив заполнен хотя бы наполовину (num ≥ size/2, а удвоение это как раз держит), 2·num ≥ size, то есть Φ ≥ 0. Условия метода выполнены. Считаем ĉ = c + Φ_после − Φ_до для двух видов вставки.

Вставка без удвоения (num было меньше size). Кладём один элемент: настоящая цена c = 1. num вырос на 1, size тот же, значит Φ вырос на 2·1 = 2. Амортизированно: ĉ = 1 + 2 = 3.

Вставка с удвоением (num = size = s до вставки). Копируем s элементов и вставляем один: c = s + 1. До: Φ_до = 2s − s = s. После: num = s + 1, size = 2s, Φ_после = 2(s+1) − 2s = 2. Амортизированно:

ĉ = c + Φ_после − Φ_до = (s + 1) + 2 − s = 3

Дорогое s из настоящей цены сократилось с падением потенциала Φ_до − Φ_после = s − 2. В обоих случаях ĉ = 3 = O(1). Значит любая серия из n вставок стоит не больше 3n - амортизированно O(1) на вставку.

Правило

Вставка в динамический массив с удвоением стоит O(1) амортизированно. Доказательство - потенциал Φ = 2·num − size: обычная вставка поднимает Φ на 2 (цена 3), вставка с удвоением роняет Φ ровно настолько, чтобы погасить копирование (цена снова 3). Запас копится, пока массив заполняется, и тратится на удвоении.

Разбор: почему именно удвоение, а не рост на константу

Пусть массив растёт не вдвое, а на фиксированные +c ячеек при каждом заполнении. Тогда n вставок вызовут n/c перестроек-расширений (это уже не удвоения), и на k-й перестройке копируется ≈ k·c элементов. Суммарное копирование: c + 2c + 3c + ... ≈ c·(n/c)²/2 = Θ(n²). На n вставок это Θ(n²), амортизированно Θ(n) на вставку - как наивный перебор. Рост на константу даёт арифметический ряд (растёт как n²), а удвоение - геометрический (1+2+4+...+n < 2n, Θ(n)). Вот почему буфер именно УДВАИВАЮТ (или множат на 1.5), а не наращивают по чуть-чуть: только геометрия превращает Θ(n) копирований в O(1) амортизированных.

Разбор: то же самое предоплатой

Проверим ответ вторым методом. Назначим вставке предоплату 3: 1 за само добавление, 2 кладём кредитом. Между двумя удвоениями (размер вырос с s/2 до s) мы сделали s/2 вставок, каждая отложила 2, - накопилось s кредита. На следующем удвоении копируем s элементов по цене 1 - ровно s, весь кредит уходит в дело и не в минус. Предоплата 3 держится, кредит неотрицателен - O(1) на вставку. Тот же ответ, что потенциалом: Φ и есть этот накопленный кредит.

Что ломается без этого

Две ошибки. Посчитать вставку по худшему случаю Θ(n) и решить, что построение массива из n элементов стоит Θ(n²), - на деле Θ(n), потому что дорогие удвоения редки. И нарастить буфер на константу ради «экономии памяти»: сэкономишь память, но вставка честно станет Θ(n) амортизированно, и заполнение массива превратится в Θ(n²) - обычная причина внезапно медленного кода.

Зачем это в работе

Это внутренность list в Python, ArrayList в Java, vector в C++, slice в Go. Все они растят буфер в постоянное число раз (у списка Python это примерно ×1.125, у ArrayList - ×1.5, часто берут ×2), и append считают O(1) именно амортизированно - доказательство ровно то, что выше и работает для любого множителя больше единицы, мы лишь взяли для счёта удвоение. Знать это нужно, когда собираешь список в цикле: append в цикле - Θ(n) на всё, а вот вставка в начало (insert(0, x)) сдвигает хвост и даёт Θ(n²). Понимание амортизации подсказывает, какая операция дёшева по серии, а какая только выглядит дешёвой.

Теперь сам

Массив с удвоением построили, вставив n элементов с нуля. Сколько стоит всё построение и сколько - одна вставка амортизированно? Почему это не Θ(n²)?

Ответ. Каждая вставка амортизированно 3 = O(1) (доказано потенциалом), значит n вставок - Θ(n) на всё построение. Не Θ(n²), потому что дорогие удвоения редки: они случаются на размерах 1, 2, 4, ..., n, и суммарное копирование 1 + 2 + ... + n < 2n = Θ(n), а не n копирований по n. Геометрический ряд удвоений - линеен, поэтому и построение линейно.

Главное

Вставка в динамический массив с удвоением - O(1) амортизированно. Потенциал Φ = 2·num − size («заполнение сверх половины»): обычная вставка поднимает Φ на 2, цена 1 + 2 = 3; вставка с удвоением (было num = size = s) копирует s, но Φ падает с s до 2, и цена снова (s+1) + 2 − s = 3. Запас копится при заполнении и тратится на удвоении. Удвоение принципиально: рост на константу дал бы арифметический ряд Θ(n²) и вставку Θ(n), а геометрический ряд удвоений - Θ(n) и вставку O(1).