Участник:Siziyman/Анализ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 18 промежуточных версий 3 участников)
Строка 5: Строка 5:
 
Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Подчеркнём, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая.  
 
Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Подчеркнём, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая.  
 
{{Определение | definition =
 
{{Определение | definition =
'''Средняя амортизационная стоимость операций''' {{---}} величина <tex>a</tex>, находящаяся по формуле: <tex dpi = "130">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>, совершённых над структурой данных.
+
'''Средняя амортизационная стоимость операций''' {{---}} величина <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>, совершённых над структурой данных.
 
}}
 
}}
 
Амортизационный анализ использует следующие методы:
 
Амортизационный анализ использует следующие методы:
Строка 23: Строка 23:
 
=====Стек с multipop=====
 
=====Стек с multipop=====
  
Рассмотрим стек с операцией <tex>\mathrm{multipop}{(a)}</tex> {{---}} извлечение из стека <tex>a</tex> элементов. В худшем случае она работает за <tex>O(n)</tex> времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более <tex>n</tex> элементов, то в худшем случае с каждым из них могли быть произведены 2 операции - добавление в стек и извлечение из него. Например, если было <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>\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>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} количество элементов, задействованных в этих операциях. Очевидно, <tex>m \leqslant n</tex> Тогда:
  
<tex dpi = "130">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> не превосходит 2, т. к. над элементом можно совершить только 2 операции, стоимость которых равна 1 {{---}} добавление и удаление. Тогда:
+
<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 dpi = "130">a \leqslant \genfrac{}{}{}{}{2m}{n} \leqslant 2,</tex> так как <tex>m \leqslant n</tex>.
+
<tex dpi = "150">a \leqslant \genfrac{}{}{}{}{2m}{n} \leqslant 2,</tex> так как <tex>m \leqslant n</tex>.
  
 
Таким образом, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.
 
Таким образом, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.
  
 
=====Двоичный счётчик=====
 
=====Двоичный счётчик=====
Рассмотрим также двоичный инкрементальный счётчик(единственная возможная операция - увеличить значение на единицу).  
+
Рассмотрим также двоичный инкрементальный счётчик (единственная возможная операция {{---}} увеличить значение на единицу).  
Пусть результат увеличения счётчика - <tex>n</tex>, тогда в худшем случае необходимо изменить значения <tex> 1 + \lfloor log n \rfloor</tex> бит, тогда стоимость <tex>n</tex> операций - <tex> O(n log n) </tex>.
+
Пусть результат увеличения счётчика {{---}} <tex>n</tex>, тогда в худшем случае необходимо изменить значения <tex> 1 + \lfloor \log n \rfloor</tex> бит, тогда стоимость <tex>n</tex> операций {{---}} <tex> O(n \log n) </tex>.
 
Теперь воспользуемся для анализа методом усреднения.
 
Теперь воспользуемся для анализа методом усреднения.
Каждый следующий бит изменяет своё значение в <tex dpi = "130">n, \genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{4} \dots</tex> операциях.
+
Каждый следующий бит изменяет своё значение в <tex dpi = "150">n, \genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{4} \dots</tex> операциях.
Общая стоимость: <tex dpi = "130"> \sum\limits_{i=0}^{\lfloor log n \rfloor} \genfrac{}{}{}{}{n}{2^i} < 2n = O(n)</tex>;
+
Общая стоимость:  
  
<tex dpi = "130"> \genfrac{}{}{}{}{O(n)}{n} = O(1) </tex>;
+
<tex dpi = "150"> \sum\limits_{i=0}^{\lfloor \log n \rfloor} \genfrac{}{}{}{}{n}{2^i} < 2n = O(n)</tex>
В итоге амортизированная стоимость одной операции - <tex>O(1)</tex>.
+
 
 +
<tex dpi = "150"> \genfrac{}{}{}{}{O(n)}{n} = O(1) </tex>
 +
 
 +
В итоге амортизированная стоимость одной операции {{---}} <tex>O(1)</tex>.
  
 
==Метод потенциалов==
 
==Метод потенциалов==
Строка 55: Строка 58:
 
2) Для любого <tex>i: \enskip \Phi_i = O(n \relax  f(n, m))</tex>
 
2) Для любого <tex>i: \enskip \Phi_i = O(n \relax  f(n, m))</tex>
 
|proof =
 
|proof =
<tex dpi = "130">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 \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 \relax O(f(n, m)) + \Phi_0 - \Phi_n}{n} = O(f(n, m))</tex>
 
}}
 
}}
  
Строка 63: Строка 66:
 
В качестве примера вновь рассмотрим стек с операцией <tex>\mathrm{multipop}{(a)}</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:
 
В качестве примера вновь рассмотрим стек с операцией <tex>\mathrm{multipop}{(a)}</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:
  
## <tex>a_{push} = 1 + 1 = 2,</tex> т. к. время выполнения операции <tex>\mathrm{push}{}</tex> {{---}} 1, и изменение потенциала {{---}} тоже 1.
+
# Амортизированная стоимость операций:
## <tex>a_{pop} = 1 - 1 = 0,</tex> т. к. время выполнения операции <tex>\mathrm{pop}{}</tex> {{---}} 1, а изменение потенциала {{---}} -1.
+
#* <tex>a_{push} = 1 + 1 = 2,</tex> так как время выполнения операции <tex>\mathrm{push}{}</tex> {{---}} <tex>1</tex>, и изменение потенциала {{---}} тоже <tex>1</tex>.
## <tex>a_{multipop} = k - k = 0,</tex> т. к. время выполнения операции <tex>\mathrm{multipop}{(k)}</tex> {{---}} k, а изменение потенциала {{---}} -k.
+
#* <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: \enskip \Phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>
 
# Для любого <tex>i: \enskip \Phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>
  
Строка 72: Строка 76:
 
=====Динамические хэш-таблицы=====
 
=====Динамические хэш-таблицы=====
  
Рассмотрим хэш-таблицы, использующие цепочки для разрешения коллизий. Для того, чтобы поиск элемента в цепочке не начал слишком сильно влиять на производительность, введём величину <tex> \alpha </tex>  {{---}} фактор загруженности(load factor) нашей таблицы.
+
Рассмотрим хэш-таблицы, использующие цепочки для разрешения коллизий. Для того, чтобы поиск элемента в цепочке не начал слишком сильно влиять на производительность, введём величину <tex> \alpha </tex>  {{---}} фактор загруженности (load factor) нашей таблицы.
Пусть в нашей таблице размером <tex> m </tex> хранится <tex> n </tex> элементов, тогда <tex dpi = "130"> \alpha = \genfrac{}{}{}{}{n}{m} </tex>
+
Пусть в нашей таблице размером <tex> m </tex> хранится <tex> n </tex> элементов, тогда <tex dpi = "150"> \alpha = \genfrac{}{}{}{}{n}{m} </tex>
Введём значение <tex>\alpha_{max}</tex>, при превышении которого таблица будет пересоздана с увеличением размера и все элементы будут перераспределены по-новому(rehashing). Аналогично будем пересоздавать таблицу с уменьшением размера при удалении элемента.
+
Введём значение <tex>\alpha_{max}</tex>, при превышении которого таблица будет пересоздана с увеличением размера и все элементы будут перераспределены по-новому (rehashing).
 
Из-за этого сложность операции <tex>\mathrm{add}{}</tex> из <tex> O(1) </tex> станет в худшем случае <tex> O(n) </tex>, так как для пересоздания таблицы нам требуется <tex> O(n) </tex> операций.
 
Из-за этого сложность операции <tex>\mathrm{add}{}</tex> из <tex> O(1) </tex> станет в худшем случае <tex> O(n) </tex>, так как для пересоздания таблицы нам требуется <tex> O(n) </tex> операций.
Стоит отметить, что изменение размера массива всегда должно быть геометрическим(в <tex> k </tex> раз), потому как при изменении размера на константу нам потребуется <tex>O(n)</tex> раз пересоздать таблицу, что приведёт к сложности операции <tex>\mathrm{add}{}</tex> в <tex> O(n^2) </tex>.
+
Стоит отметить, что изменение размера массива всегда должно быть геометрическим (в <tex> k </tex> раз), потому как при изменении размера на константу нам потребуется <tex>O(n)</tex> раз пересоздать таблицу, что приведёт к сложности операции <tex>\mathrm{add}{}</tex> в <tex> O(n^2) </tex>.
  
Введём такую потенциальную функцию, что она будет "запасать" время по мере удаления фактора загруженности от <tex dpi = "130">\genfrac{}{}{}{}{1}{2}</tex>:
+
Введём такую потенциальную функцию, что она будет "запасать" время по мере удаления фактора загруженности от <tex dpi = "150">\genfrac{}{}{}{}{1}{2}</tex>:
 
<tex> \Phi = 2|{n - m/2}| </tex>
 
<tex> \Phi = 2|{n - m/2}| </tex>
Предположим, не умаляя общности, что<tex>\alpha_{max} = 1</tex>.
+
Предположим, не умаляя общности, что <tex>\alpha_{max} = 1</tex>.
 
Теперь рассмотрим все возможные случаи для каждой из операций <tex>add, remove, find</tex>.
 
Теперь рассмотрим все возможные случаи для каждой из операций <tex>add, remove, find</tex>.
#Операция <tex>\mathrm{add}{}: n</tex> увеличивается на единицу. Следовательно, имеются три случая:
+
#<tex>\mathrm{add}{}</tex>: <tex>\, n</tex> увеличивается на единицу. Следовательно, имеются три случая:
##<tex dpi = "130">\genfrac{}{}{}{}{1}{2} \leqslant \alpha < 1 </tex>: потенциал увеличивается на 2, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.
+
#*<tex dpi = "150">\genfrac{}{}{}{}{1}{2} \leqslant \alpha < 1 </tex>: потенциал увеличивается на <tex>2</tex>, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.
##<tex dpi = "130">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.
+
#*<tex dpi = "150">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал уменьшается на <tex>2</tex>, и амортизированное время <tex> 1 - 2 = -1 </tex>.
##<tex>\alpha = 1</tex>: Таблица увеличивается в размере, так что реальная сложность {{---}} <tex> 1 + m </tex>. Но потенциал изменяется с <tex>m</tex> до нуля, следовательно амортизационная сложность {{---}} <tex> 1 + m - m = 1</tex>.
+
#*<tex>\alpha = 1</tex>: Таблица увеличивается в размере, так что реальная сложность {{---}} <tex> 1 + m </tex>. Но потенциал изменяется с <tex>m</tex> до нуля, следовательно амортизационная сложность {{---}} <tex> 1 + m - m = 1</tex>.
#<tex>\mathrm{find}{}:</tex> Потенциал не изменяется, следовательно и реальная, и амортизированная сложности {{---}} <tex>1</tex>.
+
#<tex>\mathrm{find}{}</tex>: Рассмотрим два случая:
#<tex>\mathrm{remove}{}: n</tex> уменьшается на единицу. Возможны три случая:
+
#* Элементы распределяются по таблице достаточно равномерно: время поиска элемента в списке {{---}} <tex>O(1)</tex>, потенциал не изменяется, следовательно и реальная, и амортизированная сложности {{---}} <tex>1</tex>.
##<tex dpi = "130">\genfrac{}{}{}{}{1}{2} \leqslant \alpha < 1 </tex>:  потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.
+
#* В случае, если все элементы оказываются размещены в одном списке, время поиска элемента достигает <tex>O(n)</tex>. Это время может быть улучшено до <tex>O(\log n)</tex>, если вместо списков использовать сбалансированные деревья поиска (например, в <tex>\mathrm{Java\ 8}{}</tex> ввели двоичные деревья для стандартной коллекции <tex>\mathrm{HashSet}{}</tex>).
##<tex dpi = "130">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал увеличивается на 2, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.
+
#<tex>\mathrm{remove}{}</tex>: <tex> n</tex> уменьшается на единицу. Возможны два случая:
##<tex>\alpha = 1</tex>: Таблица уменьшается в размере, следовательно реальная сложность {{---}} <tex dpi = "130"> 1 + \genfrac{}{}{}{}{m}{4}</tex>, а потенциал меняется от <tex dpi = "130">\genfrac{}{}{}{}{m}{2}</tex> до нуля, следовательно амортизированная стоимость {{---}} <tex dpi = "130"> 1 + \genfrac{}{}{}{}{m}{4} - \genfrac{}{}{}{}{m}{2} = 1 - \genfrac{}{}{}{}{m}{4}</tex>.
+
#*<tex dpi = "150">\genfrac{}{}{}{}{1}{2} \leqslant \alpha </tex>:  потенциал уменьшается на 2, и амортизированное время <tex> 1 - 2 = -1 </tex>.
 +
#*<tex dpi = "150">\alpha < \genfrac{}{}{}{}{1}{2}</tex>: потенциал увеличивается на 2, следовательно амортизированное время {{---}} <tex>1 + 2 = 3</tex>.
 +
 
  
В каждом случае амортизированное время одной операции {{---}} <tex>O(1)</tex>. Если мы создадим нашу таблицу так, что <tex dpi = "130">\alpha = \genfrac{}{}{}{}{1}{2}</tex>, то изначально потенциал будет равен нулю. И так мы будем знать, что потенциал никогда не станет меньше этого значения; в итоге амортизированная стоимость будет верхней границей реальной оценки. Следовательно, сложность последовательности из <tex> n</tex> операций будет равна <tex>O(n)</tex>.
+
В каждом случае амортизированное время одной операции в среднем случае {{---}} <tex>O(1)</tex>, в худшем случае {{---}} <tex>O(n)</tex>.  
 +
Если мы создадим нашу таблицу так, что <tex dpi = "150">\alpha = \genfrac{}{}{}{}{1}{2}</tex>, то изначально потенциал будет равен нулю. И так мы будем знать, что потенциал никогда не станет меньше этого значения; в итоге амортизированная стоимость будет верхней границей реальной оценки. Следовательно, сложность последовательности из <tex>n</tex> операций в среднем случае будет равна <tex>O(n)</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 = "130">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>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 = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \genfrac{}{}{}{}{n \cdot O(f(n, m))}{n}</tex> <tex>= O(f(n, m))</tex>.
  
 
====Примеры====
 
====Примеры====
=====Стэк с multipop=====
+
=====Стек с multipop=====
 
При выполнении операции <tex>\mathrm{push}{}</tex> будем использовать две монеты {{---}} одну для самой операции, а вторую {{---}} в качестве резерва. Тогда для операций <tex>\mathrm{pop}{}</tex> и <tex>\mathrm{multipop}{}</tex> учётную стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после операции <tex>\mathrm{push}{}</tex>.
 
При выполнении операции <tex>\mathrm{push}{}</tex> будем использовать две монеты {{---}} одну для самой операции, а вторую {{---}} в качестве резерва. Тогда для операций <tex>\mathrm{pop}{}</tex> и <tex>\mathrm{multipop}{}</tex> учётную стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после операции <tex>\mathrm{push}{}</tex>.
  
Строка 106: Строка 113:
  
 
Рассмотрим реализацию очереди на двух стеках. Пусть наши стеки имеют операции <tex>\mathrm{push}{}</tex> и <tex>\mathrm{pop}{}</tex>, обе стоимостью <tex>1</tex>.
 
Рассмотрим реализацию очереди на двух стеках. Пусть наши стеки имеют операции <tex>\mathrm{push}{}</tex> и <tex>\mathrm{pop}{}</tex>, обе стоимостью <tex>1</tex>.
Пусть каждое добавление элемента в очередь будет стоить 3 монеты. Это покроет стоимость операций <tex>\mathrm{push}{}</tex> и <tex>\mathrm{pop}{}</tex> для переноса элемента из первого стека во второй, если потребуется, и ещё 1 монета будет нужна для того, чтобы поместить элемент в первый стек. Стоимость удаления элемента из очереди {{---}} 1 монета(она потребуется нам для удаления элемента из второго стека).
+
Пусть каждое добавление элемента в очередь будет стоить <tex>3</tex> монеты, стоимость удаления элемента из очереди {{---}} <tex>1</tex> монета.
 +
 
 +
В лучшем случае(последовательность операций {{---}} добавить элемент и сразу же удалить его из очереди) мы тратим по монете непосредственно на <tex>\mathrm{push}{}</tex> в оба стека и <tex>\mathrm{pop}{}</tex> из первого стека, а стоимость удаления элемента из очереди непосредственно тратим на <tex>\mathrm{pop}{}</tex> из второго стека, и амортизированная сложность {{---}} <tex>O(1)</tex>.
 +
 
 +
Рассмотрим другой случай. Предположим, мы имеем <tex>n</tex> операций добавления элемента в очередь и операцию удаления последнего добавленного в очередь элемента. Очевидно, это потребует <tex>O(n)</tex> времени в целом. Но известно, что каждый элемент был добавлен в стеки и удалён из них не более <tex>1</tex> раза, следовательно, амортизированная стоимость каждой операции в нашей последовательности {{---}} <tex>O(1)</tex>.
  
Таким образом, амортизационная стоимость каждой операции {{---}} <tex> O(1) </tex>.
+
Таким образом, амортизационная стоимость каждой операции для очереди {{---}} <tex> O(1) </tex>.
 +
== См. также ==
 +
*[[Хеш-таблица]]
  
==Литература==
+
==Источники информации==
Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491.
+
* Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491.
 +
* [[wikipedia:Amortized_analysis | Wikipedia {{---}} Amortized analysis]]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Амортизационный анализ]]
 
[[Категория: Амортизационный анализ]]

Текущая версия на 00:50, 11 мая 2014

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

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

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

Определение:
Средняя амортизационная стоимость операций — величина [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] \genfrac{}{}{}{}{O(n)}{n} = O(1) [/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: \enskip a_i = O(f(n, m))[/math]

2) Для любого [math]i: \enskip \Phi_i = O(n \relax 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 \relax 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: \enskip \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], при превышении которого таблица будет пересоздана с увеличением размера и все элементы будут перераспределены по-новому (rehashing). Из-за этого сложность операции [math]\mathrm{add}{}[/math] из [math] O(1) [/math] станет в худшем случае [math] O(n) [/math], так как для пересоздания таблицы нам требуется [math] O(n) [/math] операций. Стоит отметить, что изменение размера массива всегда должно быть геометрическим (в [math] k [/math] раз), потому как при изменении размера на константу нам потребуется [math]O(n)[/math] раз пересоздать таблицу, что приведёт к сложности операции [math]\mathrm{add}{}[/math] в [math] O(n^2) [/math].

Введём такую потенциальную функцию, что она будет "запасать" время по мере удаления фактора загруженности от [math]\genfrac{}{}{}{}{1}{2}[/math]: [math] \Phi = 2|{n - m/2}| [/math] Предположим, не умаляя общности, что [math]\alpha_{max} = 1[/math]. Теперь рассмотрим все возможные случаи для каждой из операций [math]add, remove, find[/math].

  1. [math]\mathrm{add}{}[/math]: [math]\, n[/math] увеличивается на единицу. Следовательно, имеются три случая:
    • [math]\genfrac{}{}{}{}{1}{2} \leqslant \alpha \lt 1 [/math]: потенциал увеличивается на [math]2[/math], следовательно амортизированное время — [math]1 + 2 = 3[/math].
    • [math]\alpha \lt \genfrac{}{}{}{}{1}{2}[/math]: потенциал уменьшается на [math]2[/math], и амортизированное время [math] 1 - 2 = -1 [/math].
    • [math]\alpha = 1[/math]: Таблица увеличивается в размере, так что реальная сложность — [math] 1 + m [/math]. Но потенциал изменяется с [math]m[/math] до нуля, следовательно амортизационная сложность — [math] 1 + m - m = 1[/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]\genfrac{}{}{}{}{1}{2} \leqslant \alpha [/math]: потенциал уменьшается на 2, и амортизированное время [math] 1 - 2 = -1 [/math].
    • [math]\alpha \lt \genfrac{}{}{}{}{1}{2}[/math]: потенциал увеличивается на 2, следовательно амортизированное время — [math]1 + 2 = 3[/math].


В каждом случае амортизированное время одной операции в среднем случае — [math]O(1)[/math], в худшем случае — [math]O(n)[/math]. Если мы создадим нашу таблицу так, что [math]\alpha = \genfrac{}{}{}{}{1}{2}[/math], то изначально потенциал будет равен нулю. И так мы будем знать, что потенциал никогда не станет меньше этого значения; в итоге амортизированная стоимость будет верхней границей реальной оценки. Следовательно, сложность последовательности из [math]n[/math] операций в среднем случае будет равна [math]O(n)[/math].

Метод предоплаты

Представим, что использование определенного количества времени равносильно использованию определенного количества монет (плата за выполнение каждой операции). В методе предоплаты каждому типу операций присваивается своя учётная стоимость. Эта стоимость может быть больше фактической, в таком случае лишние монеты используются как резерв для выполнения других операций в будущем, а может быть меньше, тогда гарантируется, что текущего накопленного резерва достаточно для выполнения операции. Для доказательства оценки средней амортизационной стоимости [math]O(f(n, m))[/math] нужно построить учётные стоимости так, что для каждой операции она будет составлять [math]O(f(n, m))[/math]. Тогда для последовательности из [math]n[/math] операций суммарно будет затрачено [math]n \cdot O(f(n, m))[/math] монет, следовательно, cредняя амортизационная стоимость операций будет [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].

Очередь на двух стеках

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

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

Рассмотрим другой случай. Предположим, мы имеем [math]n[/math] операций добавления элемента в очередь и операцию удаления последнего добавленного в очередь элемента. Очевидно, это потребует [math]O(n)[/math] времени в целом. Но известно, что каждый элемент был добавлен в стеки и удалён из них не более [math]1[/math] раза, следовательно, амортизированная стоимость каждой операции в нашей последовательности — [math]O(1)[/math].

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

См. также

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

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