Что такое амортизированный анализ сложности?

Амортизированный анализ усредняет стоимость операции по последовательности: редкая дорогая операция «размазывается» на множество дешёвых, и в среднем каждая стоит мало.

Классический пример

Динамический массив: push обычно O(1), но иногда буфер удваивается с копированием за O(n). На n вставок суммарная работа пропорциональна n (каждый элемент копируется ограниченное число раз), поэтому амортизированно push — O(1).

Методы анализа

• Aggregate: считаем суммарную стоимость n операций и делим на n.
• Accounting: дешёвая операция «платит вперёд» кредит, которым оплачивается будущая дорогая.
• Potential method: стоимость выражают через потенциал структуры данных.

Отличие

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

Коротко для собеседования

Амортизированная стоимость — это суммарная цена серии операций, делённая на их число, поэтому редкие дорогие шаги вроде расширения массива не портят оценку. В отличие от среднего случая, это гарантия для любой последовательности; так же объясняют rehash в хеш-таблицах и очередь на двух стеках.