Изменения

'''Амортизационный анализ''' (англ. ''amortized analysis'') {{---}} метод подсчета подсчёта времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям, и анализируется средняя производительность операций в худшем случае.

'''Средняя амортизационная стоимость операций''' {{---}} величина <tex>a</tex>, находящаяся по формуле: <tex dpi = "150">a = \fracgenfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n}</tex>, где <tex>t_1,t_2, ... \dots t_n</tex> {{- --}} время выполнения операций <tex>1,2, ... , \dots n,</tex> , совершённых над структурой данных.

1. ==Метод усреднения (метод группового анализа).==

2. Метод потенциаловВ методе усреднения амортизационная стоимость операций определяется напрямую по формуле, указанной выше: суммарная стоимость всех операций алгоритма делится на их количество.

==Метод усреднения===Стек с multipop===== Рассмотрим [[Стек | стек]] с операцией <tex>\mathrm{multipop}{(a)}</tex> {{---}} извлечение из стека <tex>a</tex> элементов. В худшем случае она работает за <tex>O(n)</tex> времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более <tex>n</tex> элементов, то в худшем случае с каждым из них могли быть произведены две операции {{---}} добавление в стек и извлечение из него. Например, если было <tex>n</tex> операций <tex>\mathrm{push}{}</tex> {{---}} добавление в стек, стоимость каждой <tex>O(1)</tex>, и одна операция <tex>\mathrm{multipop}{(n)}</tex>, то суммарное время всех операций {{---}} <tex>O(n)</tex>, всего операций <tex>n + 1</tex>, а значит, амортизационная стоимость операции {{---}} <tex>O(1)</tex>.

В методе усреднения амортизационная стоимость Распишем приведённые рассуждения более формально.Пусть <tex>n</tex> {{---}} количество операций определяется напрямую по формуле, указанной выше: суммарная стоимость всех операций алгоритма делится на их <tex>m</tex> {{---}} количествоэлементов, задействованных в этих операциях.Очевидно, <tex>m \leqslant n</tex> Тогда:

<tex dpi ="150">a =\genfrac{}{}{}{}{\sum\limits^{n}_{i=1} {t_i}}{n} =Пример\genfrac{}{}{}{}{\sum\limits^{n}_{i=1} \sum\limits^{m}_{j=1} {t_{ij}}}{n} = \genfrac{}{}{}{}{\sum\limits^{m}_{j=1} \sum\limits^{n}_{i=Рассмотрим стек с операцией <tex>multipop(a)</tex> 1} {t_{---ij}}} извлечение из стека <tex>a</tex> элементов. В худшем случае она работает за <tex>O({n)},</tex> времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более где <tex>n{t_{ij}}</tex> элементов, то в худшем случае с каждым из них могли быть произведены 2 операции {{-- добавление в стек и извлечение из него. Например, если было <tex>n</tex> операций <tex>push</tex> - добавление в стек, }} стоимость каждой <tex>O(1)i</tex>, и одна операция -ой операции над <tex>multipop(n)j</tex>, то суммарное время всех операций - ым элементом. Величина <tex>O(2n)\sum\limits^{n}_{i=1} {t_{ij}}</tex>, всего операций не превосходит <tex>n+12</tex>, а значиттак как над элементом можно совершить только две операции, амортизационная стоимость операции - которых равна <tex>O(1)</tex>{{---}} добавление и удаление.Тогда:

Пусть <tex>n</tex> {{---}} количество Таким образом, средняя амортизационная стоимость операций, <tex>ma = O(1)</tex> {{---}} размер стека. Тогда:

<tex dpi = "150">a = \frac{\sum\limits^{n}_{i=1} {t_i}}{n} = \frac{\sum\limits^{n}_{i=1} \sum\limits^{m}_{jДвоичный счётчик====1} {t_{ij}}}{n} = \fracРассмотрим также двоичный инкрементальный счётчик (единственная возможная операция {\sum\limits^{m---}_{j=1} \sum\limits^увеличить значение на единицу). Пусть результат увеличения счётчика {n}_{i=1---} {t_{ij}}}{<tex>n},</tex> где , тогда в худшем случае необходимо изменить значения <tex>{t_{ij}}1 + \lfloor \log n \rfloor</tex> {{---}} бит, и стоимость <tex>in</tex>-ой операции над операций составит <tex>jO(n \log n) </tex>-ым элементом. Величина Теперь воспользуемся для анализа методом усреднения.Каждый следующий бит изменяет своё значение в <texdpi = "150">n, \sumgenfrac{}{}{}{}{n}{2}, \limits^genfrac{}{n}_{i=1} {t_}{ijn}{4}\dots</tex> не превосходит 2, топерациях. к. над элементом можно совершить только 2 операции, Общая стоимость которых равна 1 {{---}} добавление и удаление. Тогда:

<texdpi = "150">a \leq sum\fraclimits_{2mi=0}^{\lfloor \log n\rfloor} \leq genfrac{}{}{}{}{n}{2,^i} </tex> так как <tex>m \leq 2n = O(n)</tex>.

Таким образом, cредняя В итоге амортизационная стоимость операций одной операции {{---}} <tex>a = O(1)</tex>.

Введём для каждого состояния структуры данных величину <tex>\phiPhi</tex> {{---}} потенциал. Изначально потенциал равен <tex>\phi_0Phi_0</tex>, а после выполнения <tex>i</tex>-ой й операции {{---}} <tex>\phi_iPhi_i</tex>. Стоимость <tex>i</tex>-ой й операции обозначим <tex>a_i = t_i + \phi_i Phi_i - \phi_Phi_{i-1}</tex>. Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} размер структуры данных. Тогда средняя амортизационная стоимость операций <tex>a = O(f(n, m)),</tex> если выполнены два условия:

1) #Для любого <tex>i: \enskip a_i = O(f(n, m))</tex>2) #Для любого <tex>i: \enskip \phi_i Phi_i = O(n \relax cdot f(n, m))</tex>

<tex dpi = "150">a = \fracgenfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \fracgenfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {a_i} + \sum\limits^{n - 1}_{i = 0} {\phi_iPhi_i} - \sum\limits^{n}_{i = 1} {\phi_iPhi_i} }{n} = \fracgenfrac{}{}{}{}{n \relax cdot O(f(n, m)) + \phi_0 Phi_0 - \phi_nPhi_n}{n} = O(f(n, m))</tex>

====ПримерПримеры====В качестве примера вновь рассмотрим стек с операцией <tex>multipop(a)</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:

1.1) =====Стек с multipop=====В качестве примера вновь рассмотрим стек с операцией <tex>a_\mathrm{pushmultipop}{(a)} = 1 + 1 = 2,</tex> т. к. время выполнения операции push {{---}} 1, и изменение потенциала Пусть потенциал {{---}} тоже 1это количество элементов в стеке.Тогда:

# Амортизационная стоимость операций:#* <tex>a_{push} = 1 + 1 = 2,</tex> так как время выполнения операции <tex>\mathrm{push}{}</tex> {{---}} <tex>1</tex>, и изменение потенциала {{---}} тоже <tex>1</tex>.2) #* <tex>a_{pop} = 1 - 1 = 0,</tex> т. к. так как время выполнения операции <tex>\mathrm{pop }{}</tex> {{---}} <tex>1</tex>, а изменение потенциала {{---}} <tex>-1</tex>.#* <tex>a_{multipop} = k - k = 0,</tex> так как время выполнения операции <tex>\mathrm{multipop}{(k)}</tex> {{---}} <tex>k</tex>, а изменение потенциала {{---}} <tex>-k</tex>.# Для любого <tex>i: \Phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>

Таким образом, <tex>f(n, m) = 1.3) </tex>a_{multipop} = k + k = 0,а значит, средняя амортизационная стоимость операций </tex> т. к. время выполнения операции multipopa = O(k1) {{---}} k, а изменение потенциала {{---}} -k</tex>.

2) Для любого <tex>i: \enskip \phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>====Динамические хэш-таблицы=====

Таким образомРассмотрим [[Хеш-таблица | хэш-таблицы]], использующие цепочки в виде [[Список | списков]] для [[Разрешение коллизий | разрешения коллизий]]. Для того, чтобы поиск элемента в цепочке не начал слишком сильно влиять на производительность, введём величину <tex> \alpha </tex> {{---}} фактор загруженности (load factor) нашей таблицы.Пусть в нашей таблице размером <tex> m </tex> хранится <tex> n </tex> элементов, тогда <tex dpi = "150"> \alpha = \genfrac{}{}{}{}{n}{m} </tex>.Введём значение <tex>\alpha_{max}</tex>, при превышении которого таблица будет пересоздана с увеличением размера в <tex> 2 </tex> раза, и все элементы будут перераспределены по-новому (rehashing).Из-за этого сложность операции <tex>\mathrm{add}</tex> в худшем случае составит <tex> O(n) </tex>. Для анализа структуры введём следующую потенциальную функцию: <tex>\Phi = 2n - \alpha_{max}m </tex> Рассмотрим время работы каждой из операций <tex>\mathrm{add},\ \mathrm{remove},\ \mathrm{find}</tex>:#<tex>\mathrm{add}{}</tex>: <tex>\, n</tex> увеличивается на единицу. Следовательно, возникают два случая:#*<tex> \alpha < \alpha_{max} : \alpha_i = 1 + 2 \cdot (n + 1) - \alpha_{max} m - (2n - \alpha_{max} m) = 3</tex>, так как время выполнения операции <tex> \mathrm{add} </tex> {{---}} <tex> 1 </tex>#*<tex>\alpha = \alpha_{max} : a_i = 1 + \alpha_{max}m + 2 \cdot (\alpha_{max} m + 1) - 2\alpha_{max} m - 2 \alpha_{max} m + \alpha_{max} m = 3 </tex>, так как таблица увеличивается в размере, поэтому время работы операции <tex> \mathrm{add} </tex> составит <tex> 1 + \alpha_{max}m </tex>, потому что сейчас в таблице <tex> n = \alpha_{max} m </tex> элементов.# <tex>\mathrm{find}{}</tex>:#* Если элементы распределяются по таблице достаточно равномерно, то время поиска элемента в списке {{---}} <tex>O(1)</tex>, потенциал не изменяется, следовательно, и реальная, и амортизированная сложности {{---}} <tex>1</tex>.#* В случае, если все элементы оказываются размещены в одном списке, время поиска элемента достигает <tex>O(n)</tex>. Это время может быть улучшено до <tex>O(\log n)</tex>, если вместо списков использовать сбалансированные [[Дерево поиска, наивная реализация | деревья поиска]] (эта модификация была добавлена в <tex>\mathrm{Java\ 8}{}</tex> для стандартной коллекции <tex>\mathrm{HashSet}</tex>).#<tex>\mathrm{remove}{}</tex>: <tex> n</tex> уменьшается на единицу. Тогда амортизационное время работы с учётом изменения потенциала составит:#* <tex> a_{remove} = 1 + 2 \cdot (n - 1) - \alpha_{max} m - (2n - \alpha_{max} m) = -1 </tex> Так как <tex> \Phi_i = 2 n - \alpha_{max} m = O(n)</tex>, поэтому если <tex>f(n, m) = 1</tex>, а значит, cредняя то средняя амортизационная стоимость модифицирующих операций составит <tex>a = O(1)</tex>.

Рассмотрим метод предоплаты на примере работы саморасширяющегося массива.<br>Пусть в массиве реализованы операции <tex>push(x)</tex> - добавление элемента <tex>x</tex> в последнюю незанятую ячейку массиваТаким образом, если она есть, и операция <tex>exp(x)</tex> (от "expansion") - она выделяет память размером <tex>2n</tex>, если в массиве было <tex>n</tex> элементов, и добавляет <tex>x</tex> на <tex>n+1</tex> место в новом массиве. Покажем, что амортизированная стоимость для каждой операции <tex>exp</tex> равна требуется <tex>O(1)</tex>.<br>Представим, что использование определенного количества времени равносильно использованию определенного количества монет (плата за выполнение каждой операции). Перед использованием операции <tex>exp(x)</tex> программе необходимо выполнить <tex>n</tex> операций <tex>push(x)</tex>. Пусть на каждую операцию <tex>push(x)</tex> тратися три монеты - одна на добавление элемента в массив, одну монету будем класть рядом с элементом на место <tex>i</tex>, и еще одну на <tex>i-\frac{n}{2}</tex> место в массиве (до первого выполнения операции <tex>exp(x)</tex> эта монета никуда не кладется). К тому моменту, как нам нужно будет выполнить операцию <tex>exp(x)</tex> около каждого элемента массива будет лежать по одной монетезначит, которая и будет тратиться на его копирование во вновь созданный массив удвоенной длины. Таким образом, каждая операция <tex>push(x)</tex> стоит три монеты, а каждая операция <tex>exp(x)</tex> ничего не стоит и произвродится за счет накопленных ранее монет, т.е. ее амортизированная средняя амортизационная стоимость равна операций <tex>a = O(1)</tex>, что и требовалось доказать.

==ЛитератураИсточники информации==* [[wikipedia:Amortized_analysis | Wikipedia {{---}} Amortized analysis]]* Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491.