Асимптотика, амортизация и модель памяти: как на самом деле считать стоимость

Почти любой справочник по структурам данных начинается с таблицы: «поиск — O(1), вставка — O(n)». Эта таблица полезна ровно до того момента, когда вы впервые обнаружите, что связный список с O(1)-вставкой проигрывает массиву с O(n)-вставкой на реальных данных в десять раз. Или что «амортизированный O(1)» у вашей хеш-таблицы означает 40-миллисекундную паузу раз в минуту — ровно ту, что съедает SLA на p99.

Асимптотика — не ложь, но это очень грубая линза. Эта статья про то, как пользоваться ей строго, где у неё слепые зоны и чем их закрывать: амортизированным анализом (учёт стоимости по последовательностям операций) и моделью памяти (учёт того, что «одно обращение» — это не одна цена, а шесть разных цен, отличающихся на пять порядков).

Это фундамент для всего трека: https://courses.digitable.life/post/data-structures/00-overview/ даёт карту структур, а дальше в каждой статье мы будем считать стоимость именно теми инструментами, которые разбираются здесь.

1. Зачем вообще нужна асимптотика

Представьте, что вы сравниваете две реализации. Померили на входе из 1000 элементов: A — 3 мс, B — 5 мс. Значит ли это, что A лучше? Нет, пока вы не знаете, что произойдёт на 10 000 000. Если A растёт квадратично, а B — линейно-логарифмически, то на продакшн-нагрузке A будет считать сутки, а B — минуту.

Асимптотика отвечает ровно на один вопрос: как меняется стоимость, когда вход растёт. Она специально выбрасывает константы и младшие члены, потому что они зависят от процессора, компилятора и настроения аллокатора, а форма роста — не зависит. Это её сила и одновременно её главное ограничение. Вторая, менее очевидная функция — это язык договорённостей: когда документация std::map обещает «logarithmic in size», разработчик стандартной библиотеки не может подсунуть вам линейный поиск, даже если на маленьких размерах он быстрее, а вы имеете право проектировать систему, опираясь на этот контракт.

2. Модель вычислений: что мы вообще считаем

Прежде чем говорить «O(n)», надо договориться, что стоит единицу. Стандартная договорённость — RAM-модель (Random Access Machine):

1. Есть неограниченная память из ячеек, доступ к любой ячейке по адресу стоит 1.
2. Элементарные операции (сложение, сравнение, присваивание, разыменование) стоят 1.
3. Машинное слово вмещает w = Θ(log n) бит — достаточно, чтобы адресовать вход.

Пункты 1 и 3 — это как раз то, что чаще всего врёт на практике.

Пункт 3 важнее, чем кажется. Именно из-за него мы имеем право говорить, что сложение двух чисел — это O(1): предполагается, что числа помещаются в слово. Как только вы работаете с длинной арифметикой (Python int, BigInteger, криптография), сложение становится O(d) по числу разрядов, а умножение — O(d·log d) в лучших известных реализациях. Половина «неожиданно медленных» решений на Python — это невидимая длинная арифметика.

Пункт 1 — «доступ к любой ячейке стоит одинаково» — на современном железе неверен примерно на два порядка. Об этом весь раздел 6.

3. Строгие определения: O, Θ, Ω и почему их путают

Пусть f, g: ℕ → ℝ≥0.

• f(n) = O(g(n)) — существуют c > 0 и n₀, такие что для всех n ≥ n₀ выполнено f(n) ≤ c·g(n). Верхняя оценка. «Растёт не быстрее чем».
• f(n) = Ω(g(n)) — существуют c > 0, n₀: f(n) ≥ c·g(n) при n ≥ n₀. Нижняя оценка.
• f(n) = Θ(g(n)) — одновременно O и Ω. Точная оценка с точностью до константы.
• f(n) = o(g(n)) — для любого c > 0 найдётся n₀: f(n) < c·g(n). Строго медленнее, f/g → 0.
• f(n) = ω(g(n)) — двойственно o: f/g → ∞.

Три вещи, на которых спотыкаются постоянно.

Ошибка 1: O понимают как «точно столько». Утверждение «бинарный поиск работает за O(n²)» — формально истинно. Просто бесполезно. Когда вам нужна точность, говорите Θ. Когда говорите про алгоритм «сложность O(n log n)» — вы обещаете верхнюю границу, и это нормально; но фраза «этот алгоритм не может быть быстрее, потому что он O(n log n)» — бессмыслица.

Ошибка 2: O(...) — это множество, а знак равенства — злоупотребление нотацией. Правильнее f ∈ O(g). Именно поэтому запись читается только слева направо: n = O(n²) верно, O(n²) = n — нет. И O(n) + O(n²) = O(n²) работает, а «сократить O(n²) − O(n²) = 0» — не работает.

Ошибка 3: путают «худший случай» и асимптотическую нотацию. Это ортогональные вещи. Можно сказать «время работы быстрой сортировки в худшем случае — Θ(n²)», «в среднем — Θ(n log n)», «в лучшем — Θ(n log n)». Ω — это не «лучший случай», это нижняя граница функции, о которой идёт речь.

Классы роста, которые надо чувствовать пальцами

Практическое эмпирическое правило для одного ядра: порядка 10⁸–10⁹ простых операций в секунду. Отсюда мгновенно считается, пройдёт ли решение: n = 10⁵ и Θ(n²) — это 10¹⁰, не пройдёт; n = 10⁵ и Θ(n log n) — 1.7·10⁶, пройдёт с запасом.

Некоторые структуры дают оценки, которые выглядят как шутка. DSU с сжатием путей и объединением по рангу даёт O(α(n)) на операцию, где α — обратная функция Аккермана: α(n) ≤ 4 для любого n, которое поместится во вселенной. Формально это не константа, практически — константа. Подробный разбор в https://courses.digitable.life/post/data-structures/11-disjoint-set-union/.

4. Как считать: суммы, рекуррентности, мастер-теорема

Три техники покрывают 95% случаев.

Техника 1: суммирование по циклам. Вложенный цикл, где внутренний зависит от внешнего:

for i in range(n):
    for j in range(i, n):
        work()          # Θ(1)

Суммарно Σᵢ₌₀ⁿ⁻¹ (n − i) = n(n+1)/2 = Θ(n²). Ключевой навык — превратить структуру циклов в сумму и оценить сумму.

Техника 2: рекуррентности. Для «разделяй и властвуй» пишем T(n) = a·T(n/b) + f(n): a подзадач размера n/b, плюс f(n) на разбиение и слияние.

Мастер-теорема (CLRS, гл. 4). Пусть a ≥ 1, b > 1, и обозначим d = log_b a. Тогда:

1. Если f(n) = O(n^(d−ε)) для некоторого ε > 0 → T(n) = Θ(n^d) (доминирует рекурсия, вся работа в листьях).
2. Если f(n) = Θ(n^d · log^k n), k ≥ 0 → T(n) = Θ(n^d · log^(k+1) n) (работа равномерно размазана по уровням).
3. Если f(n) = Ω(n^(d+ε)) и выполнено условие регулярности a·f(n/b) ≤ c·f(n) для c < 1 → T(n) = Θ(f(n)) (доминирует корень).

Примеры, которые надо знать наизусть:

Мастер-теорема не покрывает неравные разбиения (T(n) = T(n/3) + T(2n/3) + n) и «щели» между случаями. Тогда — дерево рекурсии или метод подстановки.

Техника 3: дерево рекурсии. Рисуем уровни, считаем работу на каждом и складываем. Для T(n) = T(n/3) + T(2n/3) + n: на каждом уровне работа ≈ n, глубина самой длинной ветви log_{3/2} n, итого Θ(n log n). Результат затем подтверждают методом подстановки — доказательством по индукции.

5. Амортизированный анализ

Это переход от вопроса «сколько стоит одна операция» к вопросу «сколько стоит последовательность из m операций, делённая на m». Идея принадлежит Роберту Тарьяну — его статья «Amortized Computational Complexity» (1985) до сих пор лучший компактный источник.

Мотивация очевидна на динамическом массиве. Push обычно стоит 1, но раз в какое-то время массив переполняется, выделяется вдвое больший буфер и копируются все элементы — это стоит Θ(n). Сказать «push — это O(n)» формально верно, но чудовищно пессимистично: так вы получите оценку O(n²) на n пушей, тогда как реально — Θ(n).

Метод 1: агрегатный

Считаем суммарную стоимость всей последовательности и делим на количество операций.

Для n пушей в динамический массив с удвоением: копирования происходят при размерах 1, 2, 4, …, 2^k ≤ n. Суммарная стоимость копирований — геометрическая прогрессия:

1 + 2 + 4 + ... + 2^k < 2^(k+1) ≤ 2n

Плюс n единичных вставок. Итого < 3n, значит амортизированная стоимость push — не больше 3, то есть Θ(1). Ровно эту границу рисует пунктир на схеме выше.

Суть в одной фразе: геометрический рост даёт геометрическую сумму, а геометрическая сумма линейна по последнему члену. Это тот же аргумент, что делает O(1) удаление в хеш-таблице с рехешированием и O(1) добавление в буфер лога.

Метод 2: предоплата (accounting / banker’s method)

Назначаем каждой операции «условную цену» (амортизированную стоимость), которая может отличаться от реальной. Разница копится в «банке», привязанном к элементам структуры. Требование: баланс никогда не уходит в минус.

Для динамического массива: берём с каждого push 3 условных единицы. Одна тратится на саму вставку. Две кладутся «на счёт» этого элемента. При следующем удвоении надо скопировать n элементов, но половина из них (те, что добавлены после прошлого удвоения) имеют на счету по 2 монеты — и этого ровно хватает: скопировать себя и своего «старого» соседа.

Метод удобен, когда есть физическая интуиция «кто за что платит». Классический второй пример — стек с операцией multipop(k): push стоит 2 (одна за вставку, одна вперёд за будущее удаление), pop и каждый шаг multipop — 0. Отсюда сразу: любая последовательность из m операций стоит O(m), несмотря на то что один multipop может стоить O(n).

Метод 3: потенциалы

Самый мощный и самый механический. Вводим функцию потенциала Φ(D) — число, характеризующее «накопленный беспорядок» структуры. Амортизированная стоимость i-й операции:

ĉᵢ = cᵢ + Φ(Dᵢ) − Φ(Dᵢ₋₁)

Суммируя, получаем телескопирование: Σĉᵢ = Σcᵢ + Φ(D_m) − Φ(D₀). Если Φ(D_m) ≥ Φ(D₀) (обычно Φ ≥ 0 и Φ(D₀) = 0), то Σcᵢ ≤ Σĉᵢ — сумма амортизированных стоимостей ограничивает сверху реальную.

Для динамического массива берём Φ = 2·size − capacity:

• Обычный push (без реаллокации): c = 1, ΔΦ = 2. Значит ĉ = 3.
• Push с реаллокацией (size = capacity = s): c = s + 1 (скопировать s, вставить один). До: Φ = 2s − s = s. После: size = s+1, capacity = 2s, Φ = 2(s+1) − 2s = 2. Значит ĉ = (s+1) + 2 − s = 3.

Обе ветки дают 3. Это тот же результат, что и агрегатный метод, но полученный локально — без разговоров про всю последовательность. Именно поэтому метод потенциалов работает там, где агрегатный ломается: в анализе Фибоначчиевых куч (https://courses.digitable.life/post/data-structures/08-heaps-priority-queues/), splay-деревьев (https://courses.digitable.life/post/data-structures/07-balanced-trees/) и DSU.

Гистерезис: почему сжимать надо на 1/4

Соблазнительно освобождать память, как только массив заполнен меньше чем наполовину. Это классическая ловушка: последовательность push, pop, push, pop, ... на границе заставит реаллоцировать на каждой операции — амортизация умирает, получаем Θ(n) на операцию. Решение — разнести пороги: расти при 100% заполнения, сжиматься при 25%. Между порогами остаётся «зазор», за который структура успевает накопить потенциал.

Коэффициент роста: почему не всегда 2

Аргумент в пользу 1.5 тонкий и красивый. При коэффициенте 2 сумма всех ранее освобождённых блоков 1 + 2 + ... + 2^(k−1) = 2^k − 1 всегда меньше следующего запроса 2^(k+1). Аллокатор никогда не сможет переиспользовать освобождённую память под новый буфер — куча фрагментируется вверх. При коэффициенте меньше золотого сечения φ ≈ 1.618 сумма предыдущих блоков рано или поздно перекрывает следующий запрос, и память возвращается в оборот. Плата — больше реаллокаций (константа в амортизированной оценке растёт).

Главная ловушка: амортизированный ≠ предсказуемый

Амортизированная оценка — про сумму, не про распределение. O(1) амортизированно совместимо с тем, что одна операция из миллиона стоит миллион. Для батчевой обработки это неважно, для интерактивного сервиса — критично: именно эти пики формируют хвост p99/p99.9. Читайте Dean & Barroso, «The Tail at Scale», CACM 2013 — там показано, как редкие выбросы одного узла становятся типичным поведением распределённого запроса.

Практические противоядия:

• Инкрементальный рост: копировать не весь буфер сразу, а по несколько элементов на операцию (так делают incremental-rehashing хеш-таблицы, например в Redis — там две таблицы живут параллельно во время рехеша).
• Предаллокация: make([]T, 0, n), vec.reserve(n), ArrayList(capacity). Если размер известен, амортизация вообще не нужна.
• Структуры с worst-case гарантией вместо амортизированной: очередь на двух стеках с ленивым переносом → real-time queue; красно-чёрное дерево вместо splay.
• Разделение амортизированных и конкурентных гарантий — см. https://courses.digitable.life/post/data-structures/14-persistent-and-concurrent/: под блокировкой редкая дорогая операция блокирует всех.

Отличайте также амортизированный анализ от вероятностного. У хеш-таблицы «O(1) в среднем» — это про распределение хешей, и злоумышленник, знающий хеш-функцию, может выстроить коллизии и получить O(n) стабильно (hash-flooding атака). Амортизированная же оценка выполняется для любой последовательности, детерминированно. Подробности — в https://courses.digitable.life/post/data-structures/05-hash-tables/.

6. Модель памяти: где RAM-модель разваливается

Допущение «доступ к любой ячейке стоит одинаково» на современном железе неверно радикально.

Актуальные цифры удобно смотреть в интерактивной версии «Latency Numbers Every Programmer Should Know» — colin-scott.github.io.

Три принципа, из которых всё следует

1. Память передаётся блоками. Минимальная единица обмена с кэшем — кэш-линия, на x86-64 и большинстве ARM это 64 байта (у Apple M-серии — 128). Прочитали один байт — заплатили за 64. Если следующие 63 байта вам тоже нужны, промах амортизировался. Если нет — вы заплатили 64-кратную цену.

2. Пространственная локальность. Соседние по адресу данные приезжают бесплатно. Массив из 16 int32 — это ровно одна линия. Отсюда: последовательный проход по массиву в 5–20 раз быстрее указательного обхода той же длины, при идентичной асимптотике Θ(n).

3. Временна́я локальность. Недавно использованное, скорее всего, ещё в кэше. Отсюда блочные (tiled) алгоритмы: обрабатываем данные кусками, помещающимися в L2, прежде чем идти дальше.

Плюс два эффекта второго порядка. Аппаратный префетчер распознаёт последовательные и регулярные шаговые (stride) паттерны и подгружает линии заранее. Он не умеет предсказывать next = node->next — pointer chasing префетчу не поддаётся вообще. И TLB — кэш трансляции виртуальных адресов. Страница обычно 4 КБ, записей в L2 TLB порядка полутора тысяч, то есть покрытие ≈ 6 МБ. Случайный доступ по массиву в сотни мегабайт даёт промах TLB почти на каждом обращении — это дополнительный поход в память ещё до чтения самих данных. Huge pages (2 МБ) поднимают покрытие в сотни раз.

Измеряем: один и тот же Θ(n), разница в разы

import time, random, array

N = 10_000_000

# Вариант A: плотный массив машинных int64 — идеальная локальность
arr = array.array('q', range(N))

# Вариант B: связный список тех же значений через словарь-эмуляцию узлов.
# Порядок узлов в памяти перемешан — так выглядит список после
# долгой жизни в куче с вставками и удалениями.
idx = list(range(N))
random.shuffle(idx)
nxt = [0] * N            # nxt[i] — индекс следующего узла
for a, b in zip(idx, idx[1:]):
    nxt[a] = b
nxt[idx[-1]] = -1

def sum_array(a):
    return sum(a)                     # линейный проход: префетчер работает

def sum_list(nxt, start):
    s, i = 0, start
    while i != -1:                    # pointer chasing: каждый шаг — вероятный промах
        s += i
        i = nxt[i]
    return s

for name, fn, args in (("array ", sum_array, (arr,)),
                       ("list  ", sum_list, (nxt, idx[0]))):
    t = time.perf_counter()
    fn(*args)
    print(name, f"{time.perf_counter() - t:.3f} s")

Оба цикла делают Θ(n) итераций и Θ(n) сложений. На типичной машине разрыв — 3–8 раз даже на Python (где накладные расходы интерпретатора маскируют эффект); на C/Go/Rust разрыв достигает 10–20 раз. Асимптотика этой разницы не видит в принципе.

Порядок обхода матрицы

Самый наглядный пример того, что константа зависит не от алгоритма, а от раскладки данных:

import numpy as np

n = 4096
m = np.zeros((n, n), dtype=np.int64)          # C-order: строки лежат непрерывно

# шаг 8 байт — одна кэш-линия отдаёт 8 полезных значений
by_rows = lambda m: sum(int(m[i, :].sum()) for i in range(n))

# шаг 32 КБ — каждая линия отдаёт 1 значение, остальные 56 байт выброшены
by_cols = lambda m: sum(int(m[:, j].sum()) for j in range(n))

Обе функции читают ровно n² элементов. Обход по столбцам генерирует в 8 раз больше промахов кэша и, начиная с некоторого n, ещё и промахи TLB на каждом обращении. Разница на больших матрицах — 5–10 раз. Отсюда же вся тема блочного умножения матриц и struct of arrays вместо array of structs в игровых движках и колоночных СУБД (ClickHouse, DuckDB, Parquet — это ровно про пространственную локальность на масштабе диска).

Модель внешней памяти и cache-oblivious

Когда данные не помещаются в RAM, RAM-модель бесполезна совсем. Тогда переходят к модели внешней памяти (Aggarwal & Vitter, 1988): память быстрая размера M, обмен блоками размера B, стоимость измеряется в числе блоковых обменов (I/O).

В этой модели:

• Сканирование n элементов: Θ(n/B).
• Сортировка: Θ((n/B)·log_{M/B}(n/B)) — это и есть внешняя сортировка слиянием.
• Поиск: Θ(log_B n) — и вот почему СУБД используют B-деревья, а не красно-чёрные. При B = 8 КБ / 16 байт ≈ 512 дерево на миллиард ключей имеет высоту 4 вместо 30. Разница в 30 против 4 походов на диск. Разбор — в https://courses.digitable.life/post/data-structures/07-balanced-trees/.

Cache-oblivious алгоритмы (Frigo, Leiserson, Prokop, Ramachandran, 1999, PDF) достигают той же оптимальности не зная M и B — за счёт рекурсивного самоподобного разбиения, которое автоматически «попадает» в каждый уровень иерархии. Классика жанра — van Emde Boas layout дерева и рекурсивное блочное умножение матриц.

7. Скрытая цена: сколько на самом деле весит элемент

Асимптотика по памяти тоже врёт на константах, и здесь разброс ещё больше.

import sys

print(sys.getsizeof(0))          # 28 — один Python-int это 28 байт
print(sys.getsizeof([]))         # 56 — пустой список
print(sys.getsizeof([0] * 1000)) # 8056 — 8 байт на указатель + заголовок

[0] * 1000 занимает 8 КБ указателей, плюс сами объекты-числа (которые для маленьких значений закешированы, но в общем случае — по 28 байт каждый). Тот же миллион чисел:

Отсюда два практических вывода, которые постоянно недооценивают:

1. Указатель в 64-битной системе стоит столько же, сколько 8 символов текста или два float. Структура из указателей на маленькие элементы тратит на служебные данные больше, чем на полезные. Это ключевой аргумент против связных списков — см. https://courses.digitable.life/post/data-structures/03-linked-lists/.
2. Расход памяти — это расход времени. Вдвое больший объём — вдвое больше кэш-линий, вдвое больше промахов. Компактность и скорость почти всегда идут вместе, а не в противофазе. Именно поэтому compressed pointers, tagged unions, bitset-представления и вероятностные структуры (https://courses.digitable.life/post/data-structures/13-probabilistic-structures/) выигрывают не только по памяти.

8. Когда «плохая» асимптотика выигрывает

Реальные ситуации, где Θ с худшим показателем побеждает:

• Малые n. Линейный поиск по массиву из 32 элементов быстрее хеш-таблицы: нет вычисления хеша, нет разыменования, всё в двух кэш-линиях. Поэтому std::sort переключается на сортировку вставками для подмассивов < 16, а Timsort — для «прогонов» < 64.
• Огромные константы. Фибоначчиева куча даёт O(1) амортизированный decrease-key против O(log n) у бинарной, но её константа настолько велика, что в реальном Дейкстре бинарная куча обычно быстрее. Это правило, а не исключение.
• Галактические алгоритмы. Умножение матриц за O(n^2.371) (текущий рекорд в линии Coppersmith–Winograd) имеет константу, при которой преимущество наступает на матрицах, не помещающихся в наблюдаемую Вселенную. Практический потолок — Штрассен, O(n^2.807), и то от n ≈ 1000.
• Локальность против сложности. B+-дерево делает O(log_B n) обращений вместо O(log₂ n) — то же самое логарифмическое дерево, но с правильно подобранным под железо основанием.

Правило: асимптотика выбирает класс решений, замер выбирает решение внутри класса.

9. Как измерять, чтобы не обмануть себя

Асимптотику проверяют не рассуждением, а эмпирической кривой роста. Метод из Sedgewick & Wayne: удваиваем n и смотрим на отношение времён. Отношение ≈ 2 → линейно; ≈ 4 → квадратично; ≈ 2.1–2.3 → n log n.

import time
import math
from statistics import median

def doubling_test(fn, make_input, start=1000, steps=8, repeats=5):
    """Оценка показателя степени b в T(n) ~ a * n^b по отношению соседних замеров.

    Удваиваем n; если T(2n)/T(n) ≈ 2^b, то b = log2(ratio):
    b ≈ 1 → линейно, b ≈ 1.1 → n log n, b ≈ 2 → квадратично.
    """
    prev_t, n = None, start
    for _ in range(steps):
        data = make_input(n)
        samples = []
        for _ in range(repeats):
            t0 = time.perf_counter()
            fn(data)                     # результат надо «потребить», иначе его выбросят
            samples.append(time.perf_counter() - t0)
        t = median(samples)              # медиана, а не среднее: гасим GC-паузы и планировщик
        if prev_t and prev_t > 0:
            ratio = t / prev_t
            print(f"n={n:>9}  t={t:.4f}s  ratio={ratio:5.2f}  b≈{math.log2(ratio):.2f}")
        else:
            print(f"n={n:>9}  t={t:.4f}s  (прогрев)")
        prev_t = t
        n *= 2

Чек-лист, без которого замер не значит ничего:

1. Прогрев. JIT (JVM, .NET, PyPy, V8) компилирует горячий код после сотен вызовов. Первые замеры измеряют интерпретатор.
2. Повторы и медиана, а не среднее. Одно значение поймает планировщик ОС или GC-паузу.
3. Фиксировать частоту. Turbo Boost и тепловой троттлинг дают ±30% между первым и десятым прогоном. cpupower frequency-set -g performance.
4. Не давать компилятору выбросить код. Результат надо «потребить»: в Go — runtime.KeepAlive или запись в глобальную переменную, в JMH — Blackhole. И реалистичные данные: отсортированный вход и идеальное распределение хешей — это не продакшн, худший случай проверяйте отдельно.
5. Смотреть счётчики, а не только время. perf stat -e cache-misses,cache-references,dTLB-load-misses ./prog мгновенно отвечает на вопрос «это алгоритм или память?». В JVM — async-profiler, в Go — pprof.

10. Типичные ошибки — сводка

11. Как это выглядит в проде

• Redis при рехешировании держит две таблицы одновременно и переносит по несколько бакетов на каждую команду. Амортизированный O(1) превращается в worst-case почти-O(1) — ровно ради хвостовых задержек. Тот же приём — в incremental GC.
• PostgreSQL планировщик считает стоимость плана в модели внешней памяти: seq_page_cost = 1.0, random_page_cost = 4.0 — это буквально константы модели I/O, и на SSD их принято снижать до 1.1–1.5. Асимптотика в планировщике второстепенна, всё решают константы блочных обменов.
• Колоночные СУБД и форматы (ClickHouse, DuckDB, Parquet, Arrow) — это применение принципа пространственной локальности на всех уровнях сразу: агрегат по одной колонке читает только её линии/страницы, а не всю строку.
• Игровые движки переходят от array of structs к struct of arrays (ECS-архитектура): при обновлении позиций читается только массив позиций, каждая кэш-линия используется на 100%. В том же духе JVM Compressed OOPs сжимают указатели с 8 до 4 байт на кучах до 32 ГБ — чистая экономия константы, дающая на pointer-heavy коде 10–20% за счёт кэша.
• Инженерия SLA: если ваш сервис обещает p99 < 50 мс, «амортизированный O(1)» — недостаточная гарантия для контракта. Нужны либо worst-case структуры, либо вынос дорогих перестроений в фоновый поток, либо hedged requests.

12. Мини-итог

• Асимптотика отвечает на вопрос о форме роста и выбирает класс решений. O — верхняя граница, Θ — точная; путать их — источник половины некорректных утверждений.
• Считать умеют три техники: сумма по циклам, мастер-теорема, дерево рекурсии. Этого хватает почти всегда.
• Амортизированный анализ переводит вопрос с одной операции на последовательность. Три метода — агрегатный, предоплата, потенциалы; последний универсален и механичен. Амортизированный ≠ предсказуемый: пики остаются и живут в вашем p99.
• Модель памяти объясняет всё, что асимптотика объяснить не может: доступ стоит от 1 до 5 000 000 наносекунд, память ходит блоками по 64 байта, последовательный доступ на порядок дешевле случайного. Структура данных — это в первую очередь раскладка байт в памяти, и только во вторую — набор операций. Асимптотика выбирает класс решений, замер выбирает реализацию внутри класса; и то и другое обязательно.

Источники

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4-е изд. — гл. 3 (асимптотика), гл. 4 (рекуррентности и мастер-теорема), гл. 16 (амортизированный анализ). mitpress.mit.edu
• Tarjan R. E. Amortized Computational Complexity, SIAM J. Alg. Disc. Meth., 1985. doi.org/10.1137/0606031
• Sedgewick, Wayne. Algorithms, 4th ed., раздел 1.4 «Analysis of Algorithms» — метод удвоения. algs4.cs.princeton.edu/14analysis
• Skiena S. The Algorithm Design Manual, 3-е изд. — гл. 2, прикладной взгляд на анализ. algorist.com
• Drepper U. What Every Programmer Should Know About Memory, 2007 — до сих пор эталон по кэшам. PDF
• Aggarwal A., Vitter J. S. The Input/Output Complexity of Sorting and Related Problems, CACM 1988. doi.org/10.1145/48529.48535
• Frigo, Leiserson, Prokop, Ramachandran. Cache-Oblivious Algorithms, FOCS 1999. PDF
• Dean J., Barroso L. A. The Tail at Scale, CACM 2013. research.google
• Fog A. Optimization manuals — микроархитектура, латентности инструкций. agner.org/optimize
• Interactive Latency Numbers Every Programmer Should Know. colin-scott.github.io
• Исходники, которые стоит прочитать: CPython listobject.c, Go runtime/slice.go.

Что дальше

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