Асимптотический анализAsymptotic Analysis

Если измерить время работы алгоритма секундомером, результат зависит от процессора, загрузки системы, языка программирования и компилятора — сравнивать такие числа между разными алгоритмами бессмысленно. Асимптотический анализ отбрасывает всё это и оставляет только один вопрос: как число операций растёт, когда размер входа n становится очень большим? Ответ — это функция от n с точностью до константного множителя и младших слагаемых, и именно эту функцию описывают нотации O, Ω, Θ.Timing an algorithm with a stopwatch gives a result that depends on the CPU, system load, programming language, and compiler — comparing such numbers across algorithms is meaningless. Asymptotic analysis throws all of that away and keeps exactly one question: how does the operation count grow as the input size n becomes very large? The answer is a function of n up to a constant factor and lower-order terms, and that's precisely what the O, Ω, Θ notations describe.

Все четыре нотации отвечают на один и тот же вопрос — "как f(n) соотносится с g(n) при n → ∞" — но с разной строгостью границы. Путаница между ними — самая частая ошибка на собеседованиях: "алгоритм работает за O(n)" технически верно и для алгоритма, работающего за O(1), потому что O — это верхняя граница, а не точная оценка.All four notations answer the same question — "how does f(n) relate to g(n) as n → ∞" — but with a different strictness of bound. Confusing them is the most common interview mistake: "the algorithm runs in O(n)" is technically true even for an O(1) algorithm, because O is an upper bound, not an exact estimate.

На практике инженеры почти всегда говорят "O(n log n)", даже когда по смыслу имеют в виду Θ(n log n) — то есть точную, а не только верхнюю границу. Это не ошибка в быту, но на собеседовании стоит явно проговорить разницу, если алгоритм действительно доказуемо Θ, а не просто O.In practice, engineers almost always say "O(n log n)" even when they mean Θ(n log n) — a tight bound, not just an upper one. This is harmless in casual speech, but in an interview it's worth stating the difference explicitly when the algorithm is provably Θ, not merely O.

Асимптотика описывает одну операцию в худшем случае, но некоторые структуры данных дороги редко и дёшевы почти всегда — например, `push_back` в динамическом массиве (std::vector) в среднем O(1), но конкретно та вставка, что триггерит реаллокацию всего массива, стоит O(n). Амортизационный анализ отвечает не на вопрос "сколько стоит одна операция в худшем случае", а на вопрос "сколько стоит последовательность из n операций, делённая на n" — и это принципиально другая, часто более полезная гарантия.Asymptotics describes one operation in the worst case, but some data structures are rarely expensive and almost always cheap — for example, `push_back` on a dynamic array (std::vector) is O(1) on average, but the specific insertion that triggers a full-array reallocation costs O(n). Amortized analysis doesn't answer "how much does one operation cost in the worst case" but rather "how much does a sequence of n operations cost, divided by n" — a fundamentally different, often more useful guarantee.

Метод группировки (aggregate method)The aggregate method

Самый прямой способ: посчитать суммарную стоимость всех n операций и поделить на n. Для std::vector, который удваивает вместимость при переполнении: реаллокации происходят на операциях 1, 2, 4, 8, ..., то есть их суммарная стоимость — геометрическая прогрессия 1+2+4+...+n ≈ 2n. Добавить сюда n обычных вставок стоимостью O(1) каждая — итого O(n) на n операций, то есть O(1) амортизированно на операцию.The most direct approach: sum the total cost of all n operations and divide by n. For a std::vector that doubles capacity on overflow: reallocations happen at operations 1, 2, 4, 8, ..., so their total cost is the geometric series 1+2+4+...+n ≈ 2n. Add n ordinary O(1) insertions on top — total O(n) over n operations, i.e. O(1) amortized per operation.

Метод потенциалов (potential method)The potential method

Более формальный и переносимый инструмент. Вводится потенциальная функция Φ, отображающая состояние структуры данных в неотрицательное число — интуитивно, "запас прочности", накопленный структурой. Амортизированная стоимость операции i определяется как â(i) = c(i) + Φ(i) − Φ(i−1), где c(i) — реальная стоимость. Идея: дешёвые операции "платят вперёд", увеличивая Φ, а дорогая операция "расплачивается" за счёт накопленного Φ — так пик реальной стоимости гасится падением потенциала, и â(i) остаётся маленьким на каждом шаге.A more formal, more portable tool. A potential function Φ is introduced, mapping the data structure's state to a non-negative number — intuitively, the "safety margin" the structure has built up. The amortized cost of operation i is defined as â(i) = c(i) + Φ(i) − Φ(i−1), where c(i) is the real cost. The idea: cheap operations "pay ahead," raising Φ, and an expensive operation "cashes in" the accumulated Φ — so the real-cost spike is absorbed by a drop in potential, and â(i) stays small at every step.

Для std::vector: пусть Φ = 2·(размер) − (вместимость). После реаллокации размер = вместимость/2 → новая вместимость = 2·размер, значит сразу после роста Φ = 0. Перед реаллокацией размер = вместимость, значит Φ = размер — большое число, "накопленное" предыдущими дешёвыми вставками. Именно эта накопленная величина и гасит стоимость O(n) самой реаллокации в формуле â(i).For std::vector: let Φ = 2·(size) − (capacity). Right after a reallocation, size = capacity/2 → new capacity = 2·size, so Φ = 0 immediately after growth. Right before a reallocation, size = capacity, so Φ = size — a large value "saved up" by preceding cheap insertions. That saved-up value is exactly what absorbs the reallocation's O(n) cost in the â(i) formula.

// std::vector::push_back — амортизированный O(1), пиковый O(n)// std::vector::push_back — amortized O(1), worst case O(n)
void push_back(int x) {
    if (size == capacity) {
        capacity = (capacity == 0) ? 1 : capacity * 2; // O(n) редко// O(n) rarely
        reallocate_and_copy(capacity);
    }
    data[size++] = x; // O(1) почти всегда// O(1) almost always
}