Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що таке амортизована складність?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Амортизована складність** - це середня вартість однієї операції в довгій послідовності операцій над структурами даних, коли рідкісні «дорогі» кроки розподіляються по безлічі «дешевих». Вона не спирається на ймовірність, а дає гарантії на послідовності операцій. **Ключове:** класичні приклади, push у динамічний масив і dequeue/enqueue в черзі на двох стеках, працюють за O(1) амортизовано, хоча окрема операція іноді може коштувати O(n).Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь Амортизована складність - це середня вартість однієї операції в довгій послідовності операцій над структурами даних, коли рідкісні «дорогі» кроки розподіляються по безлічі «дешевих». Вона не спирається на ймовірність, а дає гарантії на послідовності операцій. Класичні приклади: push у динамічний масив і dequeue/enqueue в черзі на двох стеках - вони працюють за O(1) амортизовано, хоча окрема операція іноді може коштувати O(n). ## Детальна відповідь ### Навіщо потрібна амортизована оцінка - Рідкісні дорогі операції (наприклад, розширення масиву) не повинні «псувати» картину, якщо їхня вартість покривається безліччю дешевих операцій. - На відміну від середнього (ймовірнісного) випадку, амортизований аналіз не передбачає розподілів; він гарантує верхню межу на будь-яку послідовність операцій. - Використовується, щоб пояснити, чому інтерфейс лишається швидким «у середньому на операцію», навіть якщо окремі виклики іноді дорогі. ### Методи амортизованого аналізу 1. Агрегатний метод: рахуємо сумарну вартість T(n) усієї серії з n операцій і ділимо на n. Амортизована вартість = T(n)/n. 2. Метод бухгалтерії (accounting): призначаємо кожній операції «кредит» (умовну вартість). Дешеві операції платять трохи більше реальної ціни, утворюючи запас, який покриває рідкісні дорогі операції. 3. Метод потенціалу: вводимо функцію потенціалу Φ(стан) ≥ 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))). ### Підводні камені й застереження - Амортизована оцінка стосується довгих серій операцій; окрема операція все ще може бути дорогою. - Якщо супротивник спеціально обирає послідовності, іноді вдається «зламати» інтуїтивні оцінки, перевіряйте припущення моделі. - У системах жорсткого реального часу амортизованої константи може бути недостатньо - потрібна строга верхня межа на кожну операцію. ### Шпаргалка Амортизована вартість операції = (сумарна вартість послідовності) / (кількість операцій). Ідея: рідкісні дорогі кроки оплачуються безліччю дешевих.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.