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

Амортизована складність - це середня вартість однієї операції, якщо розглядати довгу послідовність операцій, включно з рідкісними "дорогими" випадками.

Простіше кажучи, вона показує, скільки в середньому займає операція, якщо розподілити рідкісні витрати по всіх кроках.

---

#1. Приклад: динамічний масив

Коли динамічний масив (наприклад, list у Python або vector у C++) заповнюється, він іноді розширюється:

• якщо місця вистачає → вставка займає O(1);
• якщо місце закінчилося → створюється новий масив у 2 рази більший, і всі елементи копіюються (O(n)).

Але такі копіювання відбуваються рідко: після кожного розширення знову виконуються сотні швидких вставок за O(1).

Якщо порахувати всі операції вставки за тривалий час і поділити загальний час на кількість вставок, вийде середня вартість ≈ O(1).

Це і є амортизована складність вставки - O(1).

---

#2. Аналогія

Уяви, ти йдеш дорогою, і кожен крок коштує 1 секунду, але раз на 100 кроків ти взуваєш нові черевики - витрачаєш 10 секунд. Середній час на крок усе одно залишається близько 1 секунди - це і є амортизація витрат.

---

#3. Навіщо це потрібно

Амортизована складність допомагає оцінити реальну ефективність структур даних, де:

• більшість операцій дешеві,
• але іноді трапляються рідкісні "сплески" витрат.

---

#4. Формально

Якщо за (n) операцій загальні витрати склали (T(n)), то амортизована вартість однієї операції:

[ \text{A}(n) = \frac{T(n)}{n} ]

---

Підсумок:

Амортизована складність показує середню вартість однієї операції в послідовності, згладжуючи рідкісні дорогі випадки (наприклад, при розширенні динамічного масиву).