Що таке амортизована складність?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Амортизована складність - це середня вартість однієї операції в довгій послідовності операцій над структурами даних, коли рідкісні «дорогі» кроки розподіляються по безлічі «дешевих». Вона не спирається на ймовірність, а дає гарантії на послідовності операцій. Класичні приклади: push у динамічний масив і dequeue/enqueue в черзі на двох стеках - вони працюють за O(1) амортизовано, хоча окрема операція іноді може коштувати O(n).

Детальна відповідь

Навіщо потрібна амортизована оцінка

Рідкісні дорогі операції (наприклад, розширення масиву) не повинні «псувати» картину, якщо їхня вартість покривається безліччю дешевих операцій.
На відміну від середнього (ймовірнісного) випадку, амортизований аналіз не передбачає розподілів; він гарантує верхню межу на будь-яку послідовність операцій.
Використовується, щоб пояснити, чому інтерфейс лишається швидким «у середньому на операцію», навіть якщо окремі виклики іноді дорогі.

Методи амортизованого аналізу

Агрегатний метод: рахуємо сумарну вартість T(n) усієї серії з n операцій і ділимо на n. Амортизована вартість = T(n)/n.
Метод бухгалтерії (accounting): призначаємо кожній операції «кредит» (умовну вартість). Дешеві операції платять трохи більше реальної ціни, утворюючи запас, який покриває рідкісні дорогі операції.
Метод потенціалу: вводимо функцію потенціалу Φ(стан) ≥ 0. Амортизована вартість операції i: ĉ_i = c_i + Φ(S_i) − Φ(S_{i−1}). Сума ĉ_i дає верхню межу сумарної реальної вартості.

Приклад 1: динамічний масив (push), O(1) амортизовано

Динамічний масив подвоює місткість при переповненні: звичайний push коштує O(1), але рідкісне розширення - O(n), бо потрібно скопіювати n елементів.

javascript

class DynArray {
  constructor() {
    this.capacity = 1;
    this.size = 0;
    this.data = new Array(this.capacity);
  }
  push(x) {
    if (this.size === this.capacity) {
      const newCapacity = this.capacity * 2;
      const newData = new Array(newCapacity);
      for (let i = 0; i < this.size; i++) newData[i] = this.data[i];
      this.data = newData;
      this.capacity = newCapacity;
    }
    this.data[this.size++] = x;
  }
}

Агрегатний аналіз: при подвоєнні ми копіюємо поточну кількість елементів. Якщо зробити n вставок, то кожен елемент переноситься при розширенні не більше одного разу на кожен порядок росту (1→2→4→8→...). Сумарно копіювань ≤ 2n, отже T(n) ≤ c1·n + c2·2n = O(n), а амортизована вартість push дорівнює O(1).

Потенційний аналіз (ідея): можна взяти Φ = 2·size − capacity (обрізаючи знизу нулем). Тоді звичайний push збільшує потенціал, «накопичуючи» кредит; коли відбувається розширення, реальна вартість копіювання оплачується зниженням потенціалу.

Приклад 2: черга на двох стеках, O(1) амортизовано

Дві стопки (in, out): enqueue кладе в in; dequeue бере з out, а якщо out порожній, переливає всі елементи з in в out. Переливання дороге, але кожен елемент переливається не більше одного разу, тому сумарно O(n) на n операцій, тобто O(1) амортизовано.

javascript

class Queue {
  constructor() {
    this.in = [];
    this.out = [];
  }
  enqueue(x) { this.in.push(x); }
  dequeue() {
    if (this.out.length === 0) {
      while (this.in.length) this.out.push(this.in.pop());
    }
    if (this.out.length === 0) return undefined; // порожньо
    return this.out.pop();
  }
}

Порівняння оцінок

Найгірший випадок: верхня межа для однієї операції чи входу (наприклад, push з розширенням - O(n)).
Середній випадок: математичне сподівання за розподілом входів/хешів.
Амортизований випадок: верхня межа на середню вартість за послідовністю операцій без імовірнісних припущень.

Де зустрічається на практиці

Динамічні масиви й рядки (resize з подвоєнням).
Черга на двох стеках, дек на двох списках.
Хеш-таблиці: операції вставки/пошуку - O(1) амортизовано при рідкісному rehash і контролі коефіцієнта заповнення.
Об'єднання-пошук (DSU/Union-Find) зі стисканням шляхів - майже константа амортизовано (O(α(n))).

Підводні камені й застереження

Амортизована оцінка стосується довгих серій операцій; окрема операція все ще може бути дорогою.
Якщо супротивник спеціально обирає послідовності, іноді вдається «зламати» інтуїтивні оцінки, перевіряйте припущення моделі.
У системах жорсткого реального часу амортизованої константи може бути недостатньо - потрібна строга верхня межа на кожну операцію.

Шпаргалка

Амортизована вартість операції = (сумарна вартість послідовності) / (кількість операцій). Ідея: рідкісні дорогі кроки оплачуються безліччю дешевих.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.