Амортизаційний аналіз

Амортизаційний аналіз — метод аналізу швидкодії алгоритмів, що розглядає усю послідовність операцій виконуваних програмою. Тут ми усереднюємо час необхідний для виконання операції над певною структурою даних. З амортизаційним аналізом ми можемо показати, що середній час необхідний на одну операцію нетривалий, хоча певні операції у послідовності вимагають багато часу. Амортизаційний аналіз відрізняється від аналізу середнього випадку тим, що ймовірність не має значення; амортизаційний аналіз гарантує середню швидкодію кожної операції в найгіршому випадку. Прикладами структур даних чиї операцію аналізуються за допомогою амортизаційного аналізу є геш-таблиці, неперетинні множини, розширювані дерева.

Амортизаційний аналіз початково виник з методу відомого як агрегаційний аналіз або метод групування, який наразі є одним зі способів проведення амортизаційного аналізу. Однак, формально, техніка була представлена Робертом Тар'яном у його документі 1985 року Амортизована складність обчислень, який висвітлював більш корисний різновид аналізу ніж звичайний імовірнісний аналіз.

Вступ

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

Амортизаційний аналіз подібний до аналізу середнього випадку в тому сенсі, що він цікавиться вартістю усередненою на всю послідовність операцій. Однак, аналіз середнього випадку покладається на ймовірнісні припущення щодо структури даних і алгоритму для того, щоб обчислити сподіваний час виконання алгоритму. Тобто, його використання залежить від певних припущень щодо ймовірнісного розподілу вхідних даних, з чого випливає, що оцінка не правильна якщо припущення не дотримані (або ймовірнісний аналіз не можна використовувати взагалі, якщо не можна розподіл вхідних даних). Амортизаційний аналіз не потребує таких припущень. Також він пропонує верхню межу на найгіршу швидкодію послідовності операцій, і ця межа завжди чинна. З іншого боку, межа встановлена аналізом середнього випадку не виключає, що трапиться операція з високою трудомісткістю, яка вимагатиме більше часу ніж сподіваний середній час, навіть якщо умови на розподіл дотримані. Ці відмінності між амортизаційним аналізом і аналізом середнього випадку мають важливі наслідки для інтерпретації і доречності отриманих меж.

Амортизаційний аналіз близько пов'язаний зі змаговим аналізом, який включає порівняння швидкодії найгіршого випадку онлайн алгоритму зі швидкодією оптимального оффлайн алгоритму на тих самих даних. Амортизація корисна тому, що межі встановлені конкурентним аналізом повинні бути чинними незалежно від вхідних даних, які онлайн алгоритм бачить як послідовність, а не всі одразу на початку виконання.

Метод групування

Метод групування — простий метод, який обчислює межу на послідовність операцій, тоді ділить її на кількість операцій, щоб отримати амортизаційну вартість, навіть якщо операцій різного типу (наприклад, додавання одного елементу до стеку або виштовхування декількох елементів зі стеку).

Приклад

Розглянемо стек на якому визначені три операції:

1. ${\displaystyle {\mbox{Push}}(S,x)}$ — додає елемент ${\displaystyle x}$ до стеку, потребує ${\displaystyle O(1)}$
2. ${\displaystyle {\mbox{Pop}}(S)}$ — виштовхує елемент з вершини стеку і повертає його, потребує ${\displaystyle O(1)}$
3. ${\displaystyle {\mbox{Multipop}}(S,k)}$ — виштовхує ${\displaystyle k}$ елементів зі стеку, потребує ${\displaystyle O(k)}$.

Оскільки операції ${\displaystyle {\mbox{Push}}}$ і ${\displaystyle {\mbox{Pop}}}$ мають часову складність ${\displaystyle O(1)}$ ми можемо вважати, що ціна кожної з цих операцій ${\displaystyle 1.}$ Ціна послідовності з ${\displaystyle n}$ операцій становить ${\displaystyle n.}$ Тепер додамо до послідовності операцію ${\displaystyle {\mbox{Multipop}}.}$ Часова складність цієї операції в найгіршому випадку становить ${\displaystyle O(n)}$ оскільки стек містить щонайбільше ${\displaystyle n}$ елементів. Виходить, що найгірша часова складність для всіх трьох операцій становить ${\displaystyle O(n),}$ отже послідовність у найгіршому випадку вимагає ${\displaystyle O(n^{2}).}$ Цей результат правильний але недостатньо точний.

Використовуючи метод групування, ми можемо отримати кращу оцінку. Оскільки ми можемо виштовхнути елемент зі стеку лише один раз на кожне додавання, отже, послідовність операцій ${\displaystyle {\mbox{Push}},}$ ${\displaystyle {\mbox{Pop}}}$ і ${\displaystyle {\mbox{Multipop}}}$ потребує ${\displaystyle O(n)}$ часу. З цього отримуємо середню вартість операції як ${\displaystyle O(n)/n=O(1).}$ Для отримання цієї оцінки ми не використовували ймовірнісних аргументів. Ми знайшли межу найгіршого випадку для послідовності з ${\displaystyle n}$ операцій, поділили на кількість операцій і отримали середню вартість операції або амортизаційну вартість.

Обліковий метод

Обліковий метод накладає різні вартості на різні операції, така вартість може бути більшою або меншою ніж дійсна вартість операції і називається амортизаційною вартістю. Якщо амортизаційна вартість перевищує дійсну вартість, то різниця зберігається в об'єкті, який ми називаємо передоплата. Передоплата може допомогти оплатити одну з дальших операцій, якщо її справжня вартість більша ніж амортизаційна. Цей метод відрізняється від методу групування, в якому всі операції мають однакову амортизаційну вартість.

Ми повинні гарантувати, що підсумкова амортизаційна вартість послідовності операцій є не меншою ніж підсумкова дійсна вартість послідовності операцій. Якщо позначити амортизаційну вартість ${\displaystyle i-}$ї операції як ${\displaystyle {\hat {c}}_{i},}$ тоді ми вимагаємо, щоб

${\displaystyle \sum _{i=1}^{n}{\hat {c}}_{i}\geq \sum _{i=1}^{n}c_{i}}$

для всіх можливих послідовностей. При такому записі передоплата становить ${\displaystyle \sum _{i=1}^{n}{\hat {c}}_{i}-\sum _{i=1}^{n}c_{i}.}$ І він завжди повинен бути невід'ємним.

Приклад

Для ілюстрації облікового методу можна використати приклад стека наведений вище. Дійсна вартість операцій становить:

${\displaystyle {\mbox{Push}}}$	1
${\displaystyle {\mbox{Pop}}}$	1
${\displaystyle {\mbox{Multipop}}}$	${\displaystyle \min {(k,s)}}$

Де ${\displaystyle s}$ — висота стека. Спробуємо назначити такі амортизаційні вартості:

${\displaystyle {\mbox{Push}}}$	2
${\displaystyle {\mbox{Pop}}}$	0
${\displaystyle {\mbox{Multipop}}}$	0

Оскільки на кожне додавання припадає не більше ніж одне виштовхування, за умови подвійної плати за додавання ми можемо собі дозволити не брати плату за виштовхування елементів по одному чи групами.

Метод потенціалів

Метод потенціалів представляє передоплату як потенціальну енергію або просто потенціал, який можна використовувати для оплати наступних операцій. Ми пов'язуємо потенціал з усією структурою даних над якою ми проводимо операції.

Ми проведемо ${\displaystyle n}$ операцій над структурою даних ${\displaystyle D,}$ яка початково перебуває в стані ${\displaystyle D_{0}.}$ Кожна операцій з ${\displaystyle i=1,2,\dots n}$ переводить структуру зі стану ${\displaystyle D_{i-1}}$ у стан ${\displaystyle D_{i}}$ і її дійсна вартість становить ${\displaystyle c_{i}.}$ Введемо потенціальну функцію ${\displaystyle \Phi }$, яка ставить у відповідність кожному стану дійсне число. Тоді, якщо позначити амортизаційну вартість як ${\displaystyle {\hat {c}}_{i},}$ маємо

${\displaystyle {\hat {c}}_{i}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1}).}$

З цього отримуємо амортизаційну вартість для послідовності операцій

${\displaystyle \sum _{i=1}^{n}{\hat {c}}_{i}=\sum _{i-1}^{n}c_{i}+\Phi (D_{n})-\Phi (D_{0}).}$

Якщо ми можемо визначити потенціальну функцію так, що ${\displaystyle \Phi (D_{n})\geq \Phi (D_{0}),}$ тоді підсумкова амортизаційна вартість становить верхню межу для підсумкової дійсної вартості. Оскільки ми не знаємо скільки операцій буде виконано ми повинні визначити потенціальну функцію так, щоб ${\displaystyle \forall i,\Phi (D_{i})\geq \Phi (D_{0}).}$ Зазвичай ми визначаємо ${\displaystyle \Phi (D_{0})=0.}$

Приклад

Знов розглянемо приклад зі стеком. Ми визначимо потенціальну функцію як кількість об'єктів у стеку. Для порожнього стеку ${\displaystyle \Phi (D_{0})=0}$ і після будь-якої послідовності з ${\displaystyle n}$ операцій ${\displaystyle \Phi (D_{n})\geq 0=\Phi (D_{0}).}$

Розглянемо чому дорівнюють амортизаційні вартості операцій. Для операції ${\displaystyle {\mbox{Push}}}$ різниця потенціалів становить ${\displaystyle \Phi (D_{i})-\Phi (D_{i-1})=(s+1)-s=1.}$ Отже амортизаційна вартість ${\displaystyle {\hat {c}}_{i}}$ дорівнює ${\displaystyle 1+1=2.}$ Для операцій ${\displaystyle {\mbox{Pop}}}$ і ${\displaystyle {\mbox{Multipop}}}$ маємо ${\displaystyle 0}$ і ${\displaystyle 0.}$

Примітки

1. Тар'ян, Роберт (1985). Амортизована складність обчислень. SIAM Journal on Algebraic and Discrete Methods. 6 (2): 306—318. doi:10.1137/0606031.(англ.)
2. Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 17.2 Обліковий метод. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .

Посилання

• , Принстонський університет (англ.)