Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що означає амортизована складність?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Амортизована складність** - це середня вартість однієї операції, якщо розглядати довгу послідовність операцій, включно з рідкісними "дорогими" випадками. **Ключове:** для динамічного масиву вставка в кінець має амортизовану складність O(1), бо рідкісні дорогі розширення (O(n)) розподіляються на сотні швидких вставок O(1).Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення**Амортизована складність** - це середня вартість однієї операції, якщо розглядати **довгу послідовність операцій**, включно з рідкісними "дорогими" випадками. Простіше кажучи, вона показує, **скільки в середньому займає операція, якщо розподілити рідкісні витрати по всіх кроках**. --- ### **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} ] --- **Підсумок:** > **Амортизована складність** показує *середню вартість однієї операції* в послідовності, > згладжуючи рідкісні дорогі випадки (наприклад, при розширенні динамічного масиву).Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.