Амортизаційний аналіз
Зміст
Основні визначення [ред.]
| Визначення: |
| Амортизаційний аналіз(англ.amortized analysis) - метод підрахунку часу, необхідного для виконання послідовності операцій над структурою даних. При цьому час усереднюється по всіх операціях, що виконуються, і аналізується середня продуктивність операцій у гіршому випадку. |
Такий аналіз найчастіше використовується, щоб показати, що навіть якщо деякі з операцій послідовності є дорогими, то за усереднення по всіх операціях середня їхня вартість буде невеликою за рахунок низької частоти народження. Наголосимо, що оцінка, що дається амортизаційним аналізом, не є імовірнісною: це оцінка середнього часу виконання операцій для найгіршого випадку.
| Визначення: |
| Середня амортизаційна вартість операцій— величина [math]a[/math] , що знаходиться за формулою: [math]a = \genfrac<><><><>_>[/math] , де [math]t_1,t_2 \dots t_n[/math] - час виконання операцій [math]1,2 \dots n[/math] , скоєних над структурою даних. |
Амортизаційний аналіз використовує такі методи:
- Метод усереднення (метод групового аналізу).
- Метод потенціалів.
- Метод передоплати (метод бухгалтерського обліку).
Метод усереднення [ред.]
У методі усереднення амортизаційна вартість операцій визначається безпосередньо за формулою, зазначеною вище: сумарна вартість усіх операцій алгоритму поділяється на їхню кількість.
Приклади [ред.]
Стек з multipop [ред.]
Розглянемо стек з операцією [math]\mathrm[/math] - витяг зі стеку [math]a[/math]елементів. У найгіршому випадку вона працює за [math]O(n)[/math] часу, якщо видаляються всі елементи масиву. Однак, перш ніж видалити елемент, його потрібно додати в стек. Отже, якщо в стеку було не більше [math]n[/math] елементів, то в гіршому випадку з кожним з них могли бути зроблені дві операції - додавання в стек і витяг з нього. Наприклад, якщо було [math]n[/math] операцій [math]\mathrm<>[/math] - додавання в стек, вартість кожної [math]O(1)[/math] , і одна операція [math] \mathrm[/math] , то сумарний час всіх операцій - [math]O(n)[/math] , всього операцій [math]n + 1[/math] , отже, амортизаційна вартість операції - [math]O( 1) [/ math] .
Розпишемо наведені міркування більш формально. Нехай [math]n[/math] — кількість операцій, [math]m[/math] — кількість елементів, які у цих операціях. Очевидно, [math]m \leqslant n[/math] Тоді:
[math]a = \genfrac<><><><>_ > = \genfrac<><><><>_ \sum\limits^_ >> = \genfrac<><><><>_ \sum\limits^_ >>,[/math] де [math]>[/math] — вартість [math]i [/math]-ой операції над [math]j[/math]-им елементом. Величина [math]\sum\limits^_ >[/math] не перевищує [math]2[/math] , тому що над елементом можна зробити тільки дві операції, вартість яких дорівнює [math]1[/math] - додавання та видалення. Тоді:
[math]a \leqslant \genfrac<><><><> \leqslant 2,[/math] оскільки [math]m \leqslant n[/math] .
Таким чином, середня вартість амортизаційної операцій [math]a = O(1)[/math] .
Двійковий лічильник [ред.]
Розглянемо також двійковий інкрементальний лічильник (єдина можлива операція – збільшити значення на одиницю). Нехай результатзбільшення лічильника — [math]n[/math] , тоді в гіршому випадку необхідно змінити значення [math] 1 + біт, і вартість [math]n[/math] операцій складе [ math] O (n \ log n) [/ math] . Тепер скористаємося для аналізу методом усереднення. Кожен наступний біт змінює своє значення в [math]n, \genfrac<><><><>, \genfrac<><><><> \dots[/math] операції. Загальна вартість:
Через війну амортизаційна вартість однієї операції — [math]O(1)[/math] .
Метод потенціалів [ред.]
| Теорема (Про метод потенціалів): |
| Доказ: |
| [math]\triangleright[/math] |
| [math]a = \genfrac<><><><>_>= \genfrac<><><><>_+ \sum\limits^_- \sum\limits^_>= \genfrac<><><><>= O(f(n, m))[/math] |
| [math]\triangleleft[/math] |
Приклади [ред.]
Стек з multipop [ред.]
Як приклад знову розглянемо стек з операцією [math]\mathrm[/math]. Нехай потенціал – це кількість елементів у стеку. Тоді:
- Амортизаційна вартість операцій:
- [math]a_ = 1 + 1 = 2,[/math] оскільки час виконання операції [math]\mathrm<>[/math] - [math]1[/math] , і зміна потенціалу - теж [math] 1[/math] .
- [math]a_ = 1 - 1 = 0,[/math] оскільки час виконання операції [math]\mathrm<>[/math] - [math]1[/math] , а зміна потенціалу - [math]- 1[/math] .
- [math]a_ = k - k = 0,[/math] оскільки час виконання операції [math]\mathrm[/math] - [math]k[/math] , а зміна потенціалу - [math]-k[/ math].
- Для будь-якого [math]i: \Phi_i= O(n),[/math] оскільки елементів у стеку може бути більше [math]n[/math]
Отже, [math]f(n, m) = 1[/math] , отже, середня амортизаційна вартість операцій [math]a = O(1)[/math] .
Динамічні хеш-таблиці [ред.]
Розглянемо хеш-таблиці, що використовують ланцюжки у вигляді списків для вирішення колізій. Для того, щоб пошук елемента в ланцюжку не почав сильно впливати на продуктивність, введемо величину [math] \alpha [/math] - фактор завантаженості (load factor) нашої таблиці. Нехай у нашій таблиці розміром [math] m [/math] зберігається [math] n [/math] елементів, тоді [math] \alpha = \genfrac<><><><> [/ Math] . Введемо значення [math]\alpha_[/math] , при перевищенні якого таблиця буде перетворена зі збільшенням розміру [math] 2 [/math] рази, і всі елементи будуть перерозподілені по-новому (rehashing). Через це складність операції [math]\mathrm[/math] у гіршому випадку становитиме [math] O(n) [/math] .
Для аналізу структури введемо наступну потенційну функцію: [math]\Phi = 2n - \alpha_m[/math]
Розглянемо час роботи кожної з операцій [math]\mathrm,\\mathrm,\\mathrm[/math]:
- [math]\mathrm<[/math] : [math]\, n[/math] збільшується на одиницю. Отже, виникають два випадки:
- [math] \alpha \lt \alpha_ : \alpha_i = 1 + 2 \cdot (n + 1) - \alpha_ m - (2n - \alpha_ m) = 3[/math] , оскільки час виконання операції [math] \mathrm [/math] - [math] 1 [/math]
- [math]\alpha = \alpha_ : a_i = 1 + \alpha_m + 2 \cdot (\alpha_ m + 1) - 2\alpha_ m - 2 \alpha_ m + \alpha_ m = 3 [/math] , оскільки таблиця збільшується у розмірі, тому час роботи операції [math] \mathrm [/math] складе [math] 1 + \alpha_m [/math] ,бо зараз у таблиці [math] n = \alpha_ m [/math] елементів.
- [math]\mathrm<>[/math] :
- Якщо елементи розподіляються по таблиці досить рівномірно, час пошуку елемента у списку — [math]O(1)[/math] , потенціал не змінюється, отже і реальна, і амортизована складності — [math]1[/math] .
- Якщо всі елементи опиняються в одному списку, час пошуку елемента досягає [math]O(n)[/math] . Цей час може бути покращено до [math]O(\log n)[/math] , якщо замість списків використовувати збалансовані дерева пошуку (ця модифікація була додана до [math]\mathrm<>[/math] для стандартної колекції [math] ]\mathrm[/math]).
- [math]\mathrm<>[/math] : [math] n[/math] зменшується на одиницю. Тоді амортизаційний час роботи з урахуванням зміни потенціалу становитиме:
- [math] a_ = 1 + 2 \cdot (n - 1) - \alpha_ m - (2n - \alpha_ m) = -1 [/math]
Оскільки [math] \Phi_i = 2 n - \alpha_ m = O(n)[/math] , тому якщо [math] f(n, m) = 1 [/math] , то середня амортизаційна вартість операцій, що модифікують, складе [ math] a = O(1) [/math].
Метод передоплати [ред.]
Припустимо, що використання певної кількості часу рівносильне використанню певної кількості монет (плата за виконання кожної операції). У методі передоплати кожному типу операцій присвоюється власна облікова вартість. Ця вартість може бути більшою за фактичну, у такому разі зайві монети використовуються як резерв для виконання інших операцій у майбутньому, а може бути менше, тоді гарантується, що поточного накопиченого резерву достатньо для виконання операції. Для підтвердження оцінки середньої амортизаційної вартості [math]O(f(n, m))[/math]Необхідно побудувати облікові вартості отже кожної операції вона становитиме [math]O(f(n, m))[/math] . Тоді для послідовності [math]n[/math] операцій сумарно буде витрачено [math]n \cdot O(f(n, m))[/math] монет, отже, середня амортизаційна вартість операцій буде [math]a = \ genfrac<<><><>_> = \genfrac<<><><>[/math] [math]= O(f(n, m))[/math] .
Приклади [ред.]
Стек з multipop [ред.]
При виконанні операції [math]\mathrm<[/math] будемо використовувати дві монети - одну для самої операції, а другу - як резерв. Тоді для операцій [math]\mathrm<>[/math] і [math]\mathrm<>[/math] облікову вартість можна прийняти рівною нулю і використовувати для видалення елемента монету, що залишилася після операції [math]\mathrm< >[/math] .
Отже, кожної операції потрібно [math]O(1)[/math] монет, отже, середня амортизаційна вартість операцій [math]a = O(1)[/math] .