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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 20: Строка 20:
  
 
====Пример====
 
====Пример====
Рассмотрим стек с операцией <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>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>.
  
 
Математическое обоснование:
 
Математическое обоснование:
Строка 38: Строка 38:
 
О методе потенциалов
 
О методе потенциалов
 
|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>
 
1) Для любого <tex>i: \enskip a_i = O(f(n, m))</tex>
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 = "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 = \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>
 
}}
 
}}
  
Строка 49: Строка 49:
 
В качестве примера вновь рассмотрим стек с операцией <tex>multipop(a)</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:
 
В качестве примера вновь рассмотрим стек с операцией <tex>multipop(a)</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:
  
1.1) <tex>a_{push} = 1 + 1 = 2,</tex> т. к. время выполнения операции push {{---}} 1, и изменение потенциала {{---}} тоже 1.
+
1.1) <tex>a_{push} = 1 + 1 = 2,</tex> т. к. время выполнения операции <tex>push</tex> {{---}} 1, и изменение потенциала {{---}} тоже 1.
  
1.2) <tex>a_{pop} = 1 - 1 = 0,</tex> т. к. время выполнения операции pop {{---}} 1, а изменение потенциала {{---}} -1.
+
1.2) <tex>a_{pop} = 1 - 1 = 0,</tex> т. к. время выполнения операции <tex>pop</tex> {{---}} 1, а изменение потенциала {{---}} -1.
  
1.3) <tex>a_{multipop} = k - k = 0,</tex> т. к. время выполнения операции multipop(k) {{---}} k, а изменение потенциала {{---}} -k.
+
1.3) <tex>a_{multipop} = k - k = 0,</tex> т. к. время выполнения операции <tex>multipop(k)</tex> {{---}} k, а изменение потенциала {{---}} -k.
  
2) Для любого <tex>i: \enskip \phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>
+
2) Для любого <tex>i: \enskip \Phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex>
  
 
Таким образом, <tex>f(n, m) = 1</tex>, а значит, cредняя амортизационная стоимость операций <tex>a = O(1)</tex>.
 
Таким образом, <tex>f(n, m) = 1</tex>, а значит, cредняя амортизационная стоимость операций <tex>a = O(1)</tex>.
  
 
==Метод предоплаты==
 
==Метод предоплаты==
 +
Представим, что использование определенного количества времени равносильно использованию определенного количества монет (плата за выполнение каждой операции). В методе предоплаты каждому типу операций присваивается своя учётная стоимость. Эта стоимость может быть больше фактической, в таком случае лишние монеты используются как резерв для выполнения других операций в будущем. Если получится построить учётные стоимости так, что для каждой операции она будет составлять <tex>O(f(n, m))</tex>, то и cредняя амортизационная стоимость операций будет <tex>O(f(n, m))</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>multipop(a)</tex>. При выполнении операции <tex>push</tex> будем использовать две монеты {{---}} одну для самой операции, а вторую {{---}} в качестве резерва. Тогда для операций <tex>pop</tex> и <tex>multipop</tex> учётную стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после операции <tex>push</tex>.
Представим, что использование определенного количества времени равносильно использованию определенного количества монет (плата за выполнение каждой операции). Перед использованием операции <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>O(1)</tex>, что и требовалось доказать.
+
 
 +
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, cредняя амортизационная стоимость операций <tex>a = O(1)</tex>.
  
 
==Литература==
 
==Литература==

Версия 12:53, 7 июня 2012

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

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

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

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

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

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

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

3. Метод предоплаты (метод бухгалтерского учета).

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

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

Пример

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

Математическое обоснование:

Пусть [math]n[/math] — количество операций, [math]m[/math] — количество элементов, задействованных в этих операциях. Очевидно [math]m \leq n[/math] Тогда:

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

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

Таким образом, cредняя амортизационная стоимость операций [math]a = 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 = \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))[/math]
[math]\triangleleft[/math]

Пример

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

1.1) [math]a_{push} = 1 + 1 = 2,[/math] т. к. время выполнения операции [math]push[/math] — 1, и изменение потенциала — тоже 1.

1.2) [math]a_{pop} = 1 - 1 = 0,[/math] т. к. время выполнения операции [math]pop[/math] — 1, а изменение потенциала — -1.

1.3) [math]a_{multipop} = k - k = 0,[/math] т. к. время выполнения операции [math]multipop(k)[/math] — k, а изменение потенциала — -k.

2) Для любого [math]i: \enskip \Phi_i = O(n),[/math] так как элементов в стеке не может быть больше [math]n[/math]

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

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

Представим, что использование определенного количества времени равносильно использованию определенного количества монет (плата за выполнение каждой операции). В методе предоплаты каждому типу операций присваивается своя учётная стоимость. Эта стоимость может быть больше фактической, в таком случае лишние монеты используются как резерв для выполнения других операций в будущем. Если получится построить учётные стоимости так, что для каждой операции она будет составлять [math]O(f(n, m))[/math], то и cредняя амортизационная стоимость операций будет [math]O(f(n, m))[/math].

Пример

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

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

Литература

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