Амортизационный анализ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Метод предоплаты)
м (Поправка пунктуации. ("следовательно" здесь - вводное слово, а не союз))
(не показаны 32 промежуточные версии 9 участников)
Строка 1: Строка 1:
 
==Основные определения==
 
==Основные определения==
 
{{Определение | definition =
 
{{Определение | definition =
'''Амортизационный анализ''' {{---}} метод подсчета времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям, и анализируется средняя производительность операций в худшем случае.
+
'''Амортизационный анализ''' (англ. ''amortized analysis'') {{---}} метод подсчёта времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям, и анализируется средняя производительность операций в худшем случае.
 
}}
 
}}
 
Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Подчеркнём, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая.  
 
Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Подчеркнём, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая.  
 
{{Определение | definition =
 
{{Определение | definition =
'''Средняя амортизационная стоимость операций''' {{---}} величина <tex>a</tex>, находящаяся по формуле: <tex dpi = "150">a = \frac{\sum\limits^{n}_{i = 1} {t_i}}{n}</tex>, где <tex>t_1,t_2, ... t_n</tex> - время выполнения операций <tex>1,2, ... , n,</tex> совершённых над структурой данных.
+
'''Средняя амортизационная стоимость операций''' {{---}} величина <tex>a</tex>, находящаяся по формуле: <tex dpi = 150>a = \genfrac{}{}{}{}{\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. Метод потенциалов.
+
====Примеры====
  
3. Метод предоплаты (метод бухгалтерского учета).
+
=====Стек с 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=1} {t_{ij}}}{n},</tex> где <tex>{t_{ij}}</tex> {{---}} стоимость <tex>i</tex>-ой операции над <tex>j</tex>-ым элементом. Величина <tex>\sum\limits^{n}_{i=1} {t_{ij}}</tex> не превосходит <tex>2</tex>, так как над элементом можно совершить только две операции, стоимость которых равна <tex>1</tex> {{---}} добавление и удаление. Тогда:
Рассмотрим стек с операцией <tex>multipop(a)</tex> {{---}} извлечение из стека <tex>a</tex> элементов. В худшем случае она работает за <tex>O(n)</tex> времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более <tex>n</tex> элементов, то в худшем случае с каждым из них могли быть произведены 2 операции - добавление в стек и извлечение из него. Например, если было <tex>n</tex> операций <tex>push</tex> - добавление в стек, стоимость каждой <tex>O(1)</tex>, и одна операция <tex>multipop(n)</tex>, то суммарное время всех операций {{---}} <tex>O(2n)</tex>, всего операций <tex>n + 1</tex>, а значит, амортизационная стоимость операции {{---}} <tex>O(1)</tex>.
 
  
Математическое обоснование:
+
<tex dpi = "150">a \leqslant \genfrac{}{}{}{}{2m}{n} \leqslant 2,</tex> так как <tex>m \leqslant n</tex>.
  
Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} количество элементов, задействованных в этих операциях. Очевидно <tex>m \leq n</tex> Тогда:
+
Таким образом, средняя амортизационная стоимость операций <tex>a = 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}}}{n},</tex> где <tex>{t_{ij}}</tex> {{---}} стоимость <tex>i</tex>-ой операции над <tex>j</tex>-ым элементом. Величина <tex>\sum\limits^{n}_{i=1} {t_{ij}}</tex> не превосходит 2, т. к. над элементом можно совершить только 2 операции, стоимость которых равна 1 {{---}} добавление и удаление. Тогда:
+
=====Двоичный счётчик=====
 +
Рассмотрим также двоичный инкрементальный счётчик (единственная возможная операция {{---}} увеличить значение на единицу).
 +
Пусть результат увеличения счётчика {{---}} <tex>n</tex>, тогда в худшем случае необходимо изменить значения <tex> 1 + \lfloor \log n \rfloor</tex> бит, и стоимость <tex>n</tex> операций составит <tex> O(n \log n) </tex>.
 +
Теперь воспользуемся для анализа методом усреднения.
 +
Каждый следующий бит изменяет своё значение в <tex dpi = "150">n, \genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{4} \dots</tex> операциях.
 +
Общая стоимость:  
  
<tex>a \leq \frac{2m}{n} \leq 2,</tex> так как <tex>m \leq n</tex>.
+
<tex dpi = "150"> \sum\limits_{i=0}^{\lfloor \log n \rfloor} \genfrac{}{}{}{}{n}{2^i} < 2n = O(n)</tex>
  
Таким образом, cредняя амортизационная стоимость операций <tex>a = O(1)</tex>.
+
В итоге амортизационная стоимость одной операции {{---}} <tex>O(1)</tex>.
  
 
==Метод потенциалов==
 
==Метод потенциалов==
Строка 38: Строка 48:
 
О методе потенциалов
 
О методе потенциалов
 
|statement =
 
|statement =
Введём для каждого состояния структуры данных величину <tex>\Phi</tex> {{---}} потенциал. Изначально потенциал равен <tex>\Phi_0</tex>, а после выполнения <tex>i</tex>-ой операции {{---}} <tex>\Phi_i</tex>. Стоимость <tex>i</tex>-ой операции обозначим <tex>a_i = t_i + \Phi_i - \Phi_{i-1}</tex>. Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} размер структуры данных. Тогда средняя амортизационная стоимость операций <tex>a = O(f(n, m)),</tex> если выполнены два условия:
+
Введём для каждого состояния структуры данных величину <tex>\Phi</tex> {{---}} потенциал. Изначально потенциал равен <tex>\Phi_0</tex>, а после выполнения <tex>i</tex>-й операции {{---}} <tex>\Phi_i</tex>. Стоимость <tex>i</tex>-й операции обозначим <tex>a_i = t_i + \Phi_i - \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>
+
#Для любого <tex>i: a_i = O(f(n, m))</tex>
2) Для любого <tex>i: \enskip \Phi_i = O(n \relax  f(n, m))</tex>
+
#Для любого <tex>i: \Phi_i = O(n \cdot f(n, m))</tex>
 
|proof =
 
|proof =
<tex dpi = "150">a = \frac{\sum\limits^{n}_{i = 1} {t_i}}{n} = \frac{\sum\limits^{n}_{i = 1} {a_i} + \sum\limits^{n - 1}_{i = 0} {\Phi_i} - \sum\limits^{n}_{i = 1} {\Phi_i} }{n} = \frac{n \relax O(f(n, m)) + \Phi_0 - \Phi_n}{n} = O(f(n, m))</tex>
+
<tex dpi = "150">a = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {a_i} + \sum\limits^{n - 1}_{i = 0} {\Phi_i} - \sum\limits^{n}_{i = 1} {\Phi_i} }{n} = \genfrac{}{}{}{}{n \cdot O(f(n, m)) + \Phi_0 - \Phi_n}{n} = O(f(n, m))</tex>
 
}}
 
}}
  
====Пример====
+
====Примеры====
В качестве примера вновь рассмотрим стек с операцией <tex>multipop(a)</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:
+
 
 +
=====Стек с multipop=====
 +
В качестве примера вновь рассмотрим стек с операцией <tex>\mathrm{multipop}{(a)}</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:
 +
 
 +
# Амортизационная стоимость операций:
 +
#* <tex>a_{push} = 1 + 1 = 2,</tex> так как время выполнения операции <tex>\mathrm{push}{}</tex> {{---}} <tex>1</tex>, и изменение потенциала {{---}} тоже <tex>1</tex>.
 +
#* <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</tex>, а значит, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.
  
1.1) <tex>a_{push} = 1 + 1 = 2,</tex> т. к. время выполнения операции <tex>push</tex> {{---}} 1, и изменение потенциала {{---}} тоже 1.
+
=====Динамические хэш-таблицы=====
  
1.2) <tex>a_{pop} = 1 - 1 = 0,</tex> т. к. время выполнения операции <tex>pop</tex> {{---}} 1, а изменение потенциала {{---}} -1.
+
Рассмотрим [[Хеш-таблица | хэш-таблицы]], использующие цепочки в виде [[Список | списков]] для [[Разрешение коллизий | разрешения коллизий]]. Для того, чтобы поиск элемента в цепочке не начал слишком сильно влиять на производительность, введём величину <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>.
  
1.3) <tex>a_{multipop} = k - k = 0,</tex> т. к. время выполнения операции <tex>multipop(k)</tex> {{---}} k, а изменение потенциала {{---}} -k.
+
Для анализа структуры введём следующую потенциальную функцию: <tex>\Phi = 2n - \alpha_{max}m </tex>
  
2) Для любого <tex>i: \enskip \Phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</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>f(n, m) = 1</tex>, а значит, cредняя амортизационная стоимость операций <tex>a = O(1)</tex>.
+
Так как <tex> \Phi_i = 2 n - \alpha_{max} m = O(n)</tex>, поэтому если <tex> f(n, m) = 1 </tex>, то средняя амортизационная стоимость модифицирующих операций составит <tex> a = O(1) </tex>.
  
 
==Метод предоплаты==
 
==Метод предоплаты==
Представим, что использование определенного количества времени равносильно использованию определенного количества монет (плата за выполнение каждой операции). В методе предоплаты каждому типу операций присваивается своя учётная стоимость. Эта стоимость может быть больше фактической, в таком случае лишние монеты используются как резерв для выполнения других операций в будущем, а может быть меньше, тогда гарантируется, что текущего накопленного резерва достаточно для выполнения операции. Для доказательства оценки средней амортизационной стоимости <tex>O(f(n, m))</tex> нужно построить учётные стоимости так, что для каждой операции она будет составлять <tex>O(f(n, m))</tex>. Тогда для последовательности из <tex>n</tex> операций суммарно будет затрачено <tex>n \cdot O(f(n, m))</tex> монет, следовательно, cредняя амортизационная стоимость операций будет <tex dpi = "150">a = \frac{\sum\limits^{n}_{i = 1} {t_i}}{n} = \frac{n \cdot O(f(n, m))}{n}</tex> <tex>= O(f(n, m))</tex>.
+
Представим, что использование определённого количества времени равносильно использованию определённого количества монет (плата за выполнение каждой операции). В методе предоплаты каждому типу операций присваивается своя учётная стоимость. Эта стоимость может быть больше фактической, в таком случае лишние монеты используются как резерв для выполнения других операций в будущем, а может быть меньше, тогда гарантируется, что текущего накопленного резерва достаточно для выполнения операции. Для доказательства оценки средней амортизационной стоимости <tex>O(f(n, m))</tex> нужно построить учётные стоимости так, что для каждой операции она будет составлять <tex>O(f(n, m))</tex>. Тогда для последовательности из <tex>n</tex> операций суммарно будет затрачено <tex>n \cdot O(f(n, m))</tex> монет, следовательно, средняя амортизационная стоимость операций будет <tex dpi = "150">a = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \genfrac{}{}{}{}{n \cdot O(f(n, m))}{n}</tex> <tex>= O(f(n, m))</tex>.
  
====Пример====
+
====Примеры====
Опять же рассмотрим стек с операцией <tex>multipop(a)</tex>. При выполнении операции <tex>push</tex> будем использовать две монеты {{---}} одну для самой операции, а вторую {{---}} в качестве резерва. Тогда для операций <tex>pop</tex> и <tex>multipop</tex> учётную стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после операции <tex>push</tex>.
+
=====Стек с multipop=====
 +
При выполнении операции <tex>\mathrm{push}{}</tex> будем использовать две монеты {{---}} одну для самой операции, а вторую {{---}} в качестве резерва. Тогда для операций <tex>\mathrm{pop}{}</tex> и <tex>\mathrm{multipop}{}</tex> учётную стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после операции <tex>\mathrm{push}{}</tex>.
  
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, cредняя амортизационная стоимость операций <tex>a = O(1)</tex>.
+
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, значит, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.
  
==Литература==
+
==Источники информации==
Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491.
+
* [[wikipedia:Amortized_analysis | Wikipedia {{---}} Amortized analysis]]
 +
* Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491.
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Амортизационный анализ]]
 
[[Категория: Амортизационный анализ]]

Версия 17:15, 10 июля 2019

Основные определения

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

Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Подчеркнём, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая.

Определение:
Средняя амортизационная стоимость операций — величина [math]a[/math], находящаяся по формуле: [math]a = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n}[/math], где [math]t_1,t_2 \dots t_n[/math] — время выполнения операций [math]1,2 \dots n[/math], совершённых над структурой данных.

Амортизационный анализ использует следующие методы:

  1. Метод усреднения (метод группового анализа).
  2. Метод потенциалов.
  3. Метод предоплаты (метод бухгалтерского учёта).

Метод усреднения

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

Примеры

Стек с multipop

Рассмотрим стек с операцией [math]\mathrm{multipop}{(a)}[/math] — извлечение из стека [math]a[/math] элементов. В худшем случае она работает за [math]O(n)[/math] времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более [math]n[/math] элементов, то в худшем случае с каждым из них могли быть произведены две операции — добавление в стек и извлечение из него. Например, если было [math]n[/math] операций [math]\mathrm{push}{}[/math] — добавление в стек, стоимость каждой [math]O(1)[/math], и одна операция [math]\mathrm{multipop}{(n)}[/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{}{}{}{}{\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=1} {t_{ij}}}{n},[/math] где [math]{t_{ij}}[/math] — стоимость [math]i[/math]-ой операции над [math]j[/math]-ым элементом. Величина [math]\sum\limits^{n}_{i=1} {t_{ij}}[/math] не превосходит [math]2[/math], так как над элементом можно совершить только две операции, стоимость которых равна [math]1[/math] — добавление и удаление. Тогда:

[math]a \leqslant \genfrac{}{}{}{}{2m}{n} \leqslant 2,[/math] так как [math]m \leqslant n[/math].

Таким образом, средняя амортизационная стоимость операций [math]a = O(1)[/math].

Двоичный счётчик

Рассмотрим также двоичный инкрементальный счётчик (единственная возможная операция — увеличить значение на единицу). Пусть результат увеличения счётчика — [math]n[/math], тогда в худшем случае необходимо изменить значения [math] 1 + \lfloor \log n \rfloor[/math] бит, и стоимость [math]n[/math] операций составит [math] O(n \log n) [/math]. Теперь воспользуемся для анализа методом усреднения. Каждый следующий бит изменяет своё значение в [math]n, \genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{4} \dots[/math] операциях. Общая стоимость:

[math] \sum\limits_{i=0}^{\lfloor \log n \rfloor} \genfrac{}{}{}{}{n}{2^i} \lt 2n = O(n)[/math]

В итоге амортизационная стоимость одной операции — [math]O(1)[/math].

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

Теорема (О методе потенциалов):
Введём для каждого состояния структуры данных величину [math]\Phi[/math] — потенциал. Изначально потенциал равен [math]\Phi_0[/math], а после выполнения [math]i[/math]-й операции — [math]\Phi_i[/math]. Стоимость [math]i[/math]-й операции обозначим [math]a_i = t_i + \Phi_i - \Phi_{i-1}[/math]. Пусть [math]n[/math] — количество операций, [math]m[/math] — размер структуры данных. Тогда средняя амортизационная стоимость операций [math]a = O(f(n, m)),[/math] если выполнены два условия:
  1. Для любого [math]i: a_i = O(f(n, m))[/math]
  2. Для любого [math]i: \Phi_i = O(n \cdot f(n, m))[/math]
Доказательство:
[math]\triangleright[/math]
[math]a = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {a_i} + \sum\limits^{n - 1}_{i = 0} {\Phi_i} - \sum\limits^{n}_{i = 1} {\Phi_i} }{n} = \genfrac{}{}{}{}{n \cdot O(f(n, m)) + \Phi_0 - \Phi_n}{n} = O(f(n, m))[/math]
[math]\triangleleft[/math]

Примеры

Стек с multipop

В качестве примера вновь рассмотрим стек с операцией [math]\mathrm{multipop}{(a)}[/math]. Пусть потенциал — это количество элементов в стеке. Тогда:

  1. Амортизационная стоимость операций:
    • [math]a_{push} = 1 + 1 = 2,[/math] так как время выполнения операции [math]\mathrm{push}{}[/math][math]1[/math], и изменение потенциала — тоже [math]1[/math].
    • [math]a_{pop} = 1 - 1 = 0,[/math] так как время выполнения операции [math]\mathrm{pop}{}[/math][math]1[/math], а изменение потенциала — [math]-1[/math].
    • [math]a_{multipop} = k - k = 0,[/math] так как время выполнения операции [math]\mathrm{multipop}{(k)}[/math][math]k[/math], а изменение потенциала — [math]-k[/math].
  2. Для любого [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{}{}{}{}{n}{m} [/math]. Введём значение [math]\alpha_{max}[/math], при превышении которого таблица будет пересоздана с увеличением размера в [math] 2 [/math] раза, и все элементы будут перераспределены по-новому (rehashing). Из-за этого сложность операции [math]\mathrm{add}[/math] в худшем случае составит [math] O(n) [/math].

Для анализа структуры введём следующую потенциальную функцию: [math]\Phi = 2n - \alpha_{max}m [/math]

Рассмотрим время работы каждой из операций [math]\mathrm{add},\ \mathrm{remove},\ \mathrm{find}[/math]:

  1. [math]\mathrm{add}{}[/math]: [math]\, n[/math] увеличивается на единицу. Следовательно, возникают два случая:
    • [math] \alpha \lt \alpha_{max} : \alpha_i = 1 + 2 \cdot (n + 1) - \alpha_{max} m - (2n - \alpha_{max} m) = 3[/math], так как время выполнения операции [math] \mathrm{add} [/math][math] 1 [/math]
    • [math]\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 [/math], так как таблица увеличивается в размере, поэтому время работы операции [math] \mathrm{add} [/math] составит [math] 1 + \alpha_{max}m [/math], потому что сейчас в таблице [math] n = \alpha_{max} m [/math] элементов.
  2. [math]\mathrm{find}{}[/math]:
    • Если элементы распределяются по таблице достаточно равномерно, то время поиска элемента в списке — [math]O(1)[/math], потенциал не изменяется, следовательно, и реальная, и амортизированная сложности — [math]1[/math].
    • В случае, если все элементы оказываются размещены в одном списке, время поиска элемента достигает [math]O(n)[/math]. Это время может быть улучшено до [math]O(\log n)[/math], если вместо списков использовать сбалансированные деревья поиска (эта модификация была добавлена в [math]\mathrm{Java\ 8}{}[/math] для стандартной коллекции [math]\mathrm{HashSet}[/math]).
  3. [math]\mathrm{remove}{}[/math]: [math] n[/math] уменьшается на единицу. Тогда амортизационное время работы с учётом изменения потенциала составит:
    • [math] a_{remove} = 1 + 2 \cdot (n - 1) - \alpha_{max} m - (2n - \alpha_{max} m) = -1 [/math]

Так как [math] \Phi_i = 2 n - \alpha_{max} 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{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \genfrac{}{}{}{}{n \cdot O(f(n, m))}{n}[/math] [math]= O(f(n, m))[/math].

Примеры

Стек с multipop

При выполнении операции [math]\mathrm{push}{}[/math] будем использовать две монеты — одну для самой операции, а вторую — в качестве резерва. Тогда для операций [math]\mathrm{pop}{}[/math] и [math]\mathrm{multipop}{}[/math] учётную стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после операции [math]\mathrm{push}{}[/math].

Таким образом, для каждой операции требуется [math]O(1)[/math] монет, значит, средняя амортизационная стоимость операций [math]a = O(1)[/math].

Источники информации

  • Wikipedia — Amortized analysis
  • Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491.