Первая страница / Теория / Построение и анализ алгоритмов /

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

Голосование: 14, 5

Введение

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

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

  • если исполняется некоторая последовательность операций над структурой данных (причём до этого структура данных находилась в начальном состоянии — стек был пуст и т. п.), то фактическая суммарная длительность всех операций не превосходит суммы их учётных стоимостей.

Если это условие выполнено, то говорят, что учётные стоимости присвоены корректно. Заметим, что для одной и той же структуры данных и одних и тех же алгоритмов выполнения операций можно корректно назначить учётные стоимости несколькими различными способами.

Далее мы рассмотрим три основные метода амортизационного анализа:

  • метод группировки
  • метод предоплаты
  • метод потенциалов

Эти методы мы проиллюстрируем на двух примерах:

  • стек, снабженный дополнительной операцией Multipop, удаляющий из стека несколько элементов одновременно
  • двоичный счетчик, снабженный единственной операцией Increment (увеличить на единицу).

Метод группировки

Метод группировки (aggregate method) состоит в следующем:

  • мы можем оценить стоимость n операций в худшем случае и установить, что она не превосходит T(n)

Время в расчёте на одну операцию, то есть отношение T(n) ⁄ n, объявляется учётной стоимостью одной операции. При этом учётные стоимости всех операций оказываются одинаковыми.

Пример одинаковых учетных стоимостей операций

Операции со стеком

Мы применим метод группировки для анализа стека с одной дополнительной операцией. Ранее мы ввели две основные операции со стеком:

  • Push(S,x) добавляет элемент х к стеку S;
  • Pop(S) удаляет вершину стека S (и возвращает её);

Каждая из этих операций выполняется за время O(1). Следовательно, выполнение n операций Push и Pop требует времени Ω(n).

Ситуация становится более интересной, если добавить операцию Multipop(S,k), которая удаляет k элементов из стека (если в стеке содержится менее k элементов, то удаляется всё, что там есть).

При применении операции Multipop(S,k) к стеку, содержащему s элементов, будет произведено min(s,k) операций Pop. Поэтому (имеется в виду фактическая стоимость, а не учётная) время её работы пропорционально min(s, k).

Считая, что операции Push, Pop имеют единичную стоимость (имеется в виду фактическая стоимость, а не учётная), а операция Multipop имеет стоимость min(s,k), оценим суммарную стоимость n операций, применённых к изначально пустому стеку.

Стоимость любой из операций не превосходит n (самая дорогая операция Multipop стоит не более n, поскольку за n операций в стеке не наберётся более n элементов). Следовательно, суммарная стоимость n операций есть O(n2).

Эта оценка слишком груба. Чтобы получить точную оценку, заметим, что первоначально стек был пуст, общее число реально выполняемых операций Pop (включая те из них, что вызываются из процедуры Multipop) не превосходит общего числа операций Push, а это последнее не превосходит n. Стало быть, стоимость любой последовательности из n операций Push, Pop и Multipop, применённых к пустому стеку, есть O(n).

Тем самым можно объявить, что учётная стоимость каждой из операций есть: O(n) ⁄ n = O(1)

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

Далее мы применим метод группировки к анализу k-битового двоичного счётчика. Счётчик реализован как массив битов A[0…k−1] и хранит двоичную запись числа

x = ∑i=0…k−1A[i]2i

(так что A[0] — младший бит). Первоначально х = 0, т. е. А[i] = 0 для всех i.

Определим операцию Increment (увеличить на 1 по модулю 2k).

Стоимость операции Increment линейно зависит от общего количества битов, подвергшихся изменению (очистке или установке). Отсюда сразу получается грубая оценка: поскольку в худшем случае (массив А состоит из одних единиц) меняются k битов, требуется O(nk) операций, чтобы сосчитать от 0 до n. Чтобы получить более точную оценку, заметим, что не каждый раз значения всех k битов меняются.

Пример работы двоичного счетчика

В самом деле, младший бит A[0] меняется при каждом исполнении операции Increment. Следующий по старшинству бит А[1] меняется только через раз: при отсчёте от нуля до n этот бит меняется [n⁄2] раз. Далее, A[2] меняется только каждый четвёртый раз, и так далее.

Если 0 ≤ i ≤ [logn], то в процессе счёта от 0 до n бит А[i] меняется [n⁄2i] раз, а если i > [logn], то бит А[i] вообще не меняется. Стало быть, общее количество операций очистки и установки битов равно

i=0…[logn] [n⁄2i] < ni=0…∞ 1⁄2i = 2n

Тем самым увеличение двоичного счётчика от 0 до n требует в худшем случае O(n) операций, причём константа не зависит от k (и равна 2); учётную стоимость каждой операции можно считать равной O(n)⁄n = O(1) (константа опять же не зависит от k).

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

При проведении амортизационного анализа по методу предоплаты (accounting method) каждой операции присваивается своя учётная стоимость, причём эти стоимости могут быть как больше, так и меньше реальных. Если учётная стоимость превосходит реальную, разность рассматривается как резерв (credit), который считается связанным с каким-то объектом структуры данных и рассматривается как предоплата за будущую обработку этого объекта. За счёт этого резерва компенсируется разница между учётной и реальной стоимостью для тех операций, у которых учётная стоимость ниже реальной.

Мы должны выбирать учётные стоимости так, чтобы сумма фактических стоимостей не превосходила суммы учётных стоимостей, то есть чтобы резерв оставался неотрицательным в любой момент работы.

Операции со стеком

Проиллюстрируем метод предоплаты на уже известном нам примере со стеком. Напомним, что реальные стоимости операций со стеком мы считаем такими:

Push1
Pop1
Multipopmin(s,k)

где k — количество элементов, удаляемых из стека, s — размер стека. Присвоим этим операциям такие учётные стоимости:

Push2
Pop0
Multipop0

Покажем теперь, что выбранные нами учётные стоимости позволяют полностью покрыть реальную стоимость операций со стеком.

Будем считать, что единицей стоимости операций является доллар. Воспользуемся аналогией между стеком и стопкой тарелок Первоначально ни одной тарелки в стопке нет (мы начинаем с пустого стека). Когда мы добавляем тарелку к стопке, мы должны заплатить 1 доллар за операцию Push (это её реальная цена). Один доллар остается у нас в резерве, ведь учётная цена операции Push равна двум долларам. Будем всякий раз класть этот резервный доллар на соответствующую тарелку. Тогда в каждый момент на каждой тарелке в нашей стопке будет лежать по долларовой бумажке.

Доллар, лежащий на тарелке, — это предоплата за удаление тарелки из стопки. Благодаря этому операция Pop становится бесплатной (учётная стоимость Pop равна нулю), поскольку за удаление тарелки можно расплатиться лежащим на ней резервным долларом. Точно так же мы имеем возможность объявить операцию Multipop бесплатной: если надо удалить k тарелок, за удаление каждой из них мы расплатимся лежащим на ней долларом.

Стало быть, избыточная плата за операцию Push покрывает расходы на операции Pop и Multipop (стоимость любой последовательности из n операций Push, Pop и Multipop не превосходит суммарной учётной стоимости).

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

Решим таким же способом задачу о двоичном счётчике. Нам надо провести амортизационный анализ последовательности из n операций Increment (в исходном состоянии в счётчике записан нуль). Мы уже отмечали, что время работы этой операции пропорционально суммарному количеству установок и очисток битов. Будем считать, что каждая установка или очистка стоит 1 доллар. Установим такие учётные стоимости:

  • 2 доллара за установку бита
  • 0 за очистку

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

Теперь легко определить учётную стоимость операции Increment: поскольку каждая такая операция требует не более одной установки бита, ее учётную стоимость можно считать равной 2 долларам. Следовательно, фактическая стоимость n последовательных операций Increment, начинающихся с нуля, есть O(n), поскольку она не превосходит суммы учётных стоимостей.

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

Метод потенциалов (potential method) является обобщением метода предоплаты: здесь резерв не распределяется между отдельными элементами структуры данных (например, отдельными битами двоичного счётчика), а является функцией состояния структуры данных в целом. Эта функция называется "потенциальной энергией", или "потенциалом".

Общая схема метода потенциалов такова. Пусть над структурой данных предстоит произвести n операций, и пусть Di — состояние структуры данных после i-й операции (в частности, D0 — исходное состояние).

Потенциал (potential) представляет собой функцию F из множества возможных состояний структуры данных во множество действительных чисел; эта функция называется ещё потенциальной функцией (potential function). Пусть ci — реальная стоимость i-й операции.

Учётной стоимостью i-й операции объявим число

c*i = ci + F(Di) − F(Di−1)  (1)

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

i=1…n c*i = ∑i=1…n ci + F(Dn) − F(D0) (2)

Если нам удалось придумать функцию F, для которой F(Dn) ≥ F(D0), то суммарная учётная стоимость даст верхнюю оценку для реальной стоимости последовательности n операций. Не ограничивая общности, можно считать, что F(D0) = 0.

Иначе говоря, если разность потенциалов F(Di) − F(Di − 1) положительна, то учётная стоимость i-й операции включает в себя резерв ("предоплату" за будущие операции); если же эта разность отрицательна, то учётная стоимость i-й операции меньше реальной, и разница покрывается за счет накопленного к этому моменту потенциала.

Операции со стеком

Проиллюстрируем метод потенциалов на примере знакомой нам задачи о стеке с операциями Push, Pop и Multipop В качестве потенциальной функции F возьмём количество элементов в стеке. Поскольку мы начинаем с пустого стека, имеем

F(Dn) ≥ 0 = F(D0)

Стало быть, сумма учётных стоимостей оценивает сверху реальную стоимость последовательности операций.

Найдём теперь учётные стоимости индивидуальных операций. Так как операция Push имеет реальную стоимость 1 и к тому же увеличивает потенциал на 1, её учётная стоимость равна 1 + 1 = 2; операция Multipop, удаляющая из стека m элементов, имеет стоимость m, но уменьшает потенциал на m, так что её учётная стоимость равна m − m = 0; точно так же равна нулю и учётная стоимость операции Pop. Коль скоро учётная стоимость каждой операции не превосходит 2, стоимость последовательности n операций, начинающихся с пустого стека, есть O(n).

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

Проанализируем с помощью метода потенциалов двоичный счётчик. В качестве потенциальной функции возьмём количество единичных битов в счётчике.

Найдем учётную стоимость операции Increment. Пусть bi — количество единиц в счётчике после i-й операции, и пусть i-я операция Increment очищает ti битов; тогда bi ≤ bi−1 − ti + 1 (кроме очистки битов, Increment может ещё установить в единицу не более одного бита). Стало быть, фактическая стоимость i-й операции Increment не превосходит ti + 1, а её учётная стоимость есть:

c*i ≤ (ti + 1) + (bi − bi − 1)

Если отсчёт начинается с нуля, то F(D0) = 0, так что F(Di) ≥ F(D0), для всех i, сумма учётных стоимостей оценивает сверху сумму фактических стоимостей, и суммарная стоимость n операций Increment есть O(n) с константой (2), не зависящей от k (размера счётчика).

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

i=1…n ci = ∑i=1…n c*i − F(Dn) + F(D0)

откуда, принимая во внимание, что c*i ≤ 2 для всех i, получаем, что

i=1…n ci ≤ 2n − bn + b0

Поскольку b0 ≤ k, для достаточно длинных последовательностей операций фактическая стоимость оценивается как O(n), причём константа в O-записи не зависит ни от k, ни от начального значения счетчика.

Динамические таблицы

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

Будем считать, что динамическая таблица поддерживает операции Table-Insert (добавить к таблице) и Table-Delete (удалить из таблицы). При добавлении записи к таблице мы занимаем в таблице одну ячейку (slot), при удалении записи одна ячейка освобождается.

Коэффициентом заполнения (load factor) таблицы T называют число α(T), равное отношению числа заполненных ячеек к размеру таблицы (общему числу ячеек), если знаменатель отличен от нуля. Для вырожденной таблицы (не содержащей ни одной ячейки) коэффициент заполнения мы считаем равным единице. Если определенный таким образом коэффициент заполнения ограничен снизу положительным числом, то доля свободных ячеек в таблице ограничена сверху числом, меньшим единицы.

Расширение таблицы

Для начала рассмотрим динамическую таблицу, в которую можно добавлять записи, но нельзя удалять. Память для таблицы выделяется в виде массива ячеек. Таблица заполнена, когда в ней нет свободных ячеек (иными словами, когда коэффициент заполнения равен 1).

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

Как показывает опыт, разумно увеличивать таблицу в момент переполнения вдвое. Если мы только добавляем записи к таблице, то при такой стратегии коэффициент заполнения не может стать меньше 1⁄2 (если он не был таким в самом начале), т. е. пустые ячейки не будут занимать более половины таблицы.

Вот как выглядит алгоритм Table-Insert, основанный на этих принципах (table[T] — указатель на блок памяти, в котором размещена таблица T, num[T] — количество записей в таблице, size[T] — размер таблицы, т. е. количество ячеек; первоначально size[T] = num[T] = 0):

Table-Insert(T,x):
if size[T] = 0
    then выделить блок table[T] с одной ячейкой
              size[T] := 1
if num[T] = size[T]
 then   выделить блок памяти new-table с 2size[T] ячейками
        скопировать все записи из table[T] в new-table
освободить память, занятую table[T]
            table[T] := new-table
            size[T] := 2size[T]
записать х в table[T]
num[T] := num[T] + 1

Проанализируем время работы этого алгоритма. Собственно запись в таблицу происходит в нём только тогда, когда мы копируем старую таблицу в новую и добавляем элемент в таблицу. Стоимость операции "записать элемент в таблицу" примем за единицу. Будем считать, что время работы всей процедуры Table-Insert пропорционально количеству операций "записать в таблицу"; тем самым мы подразумеваем, что затраты на выделение памяти под таблицу с одной ячейкой — величина ограниченная, и что затраты на выделение и освобождение памяти — величина не большего порядка, чем затраты на переписывание из одной таблицы в другую.

Пусть теперь мы применили n операций Table-Insert к таблице, не содержащей первоначально ни одной ячейки. Какова стоимость i-й операции, после которой в таблице будет i элементов? Обозначим эту стоимость через ci. Если в таблице есть место (или если i = 1), то ci = 1 (мы записываем новый элемент в таблицу один раз). Если же места в таблице нет и добавление записи к таблице сопровождается расширением таблицы, то ci = i: одна единица стоимости идёт на запись нового элемента в расширенную таблицу, и ещё i — единица пойдёт на копирование старой таблицы в новую.

Стало быть, ci ≤ n при всех i, и грубая оценка стоимости n операций Table-Insert есть O(n2). Можно, однако, эту оценку улучшить, если проследить, сколь часто происходит расширение таблицы. Расширение происходит только в том случае, когда i − 1 является степенью двойки, так что

i=1…n ci ≤ ∑j=0…log[n]2j < n + 2n = 3n

Стало быть, стоимость n операций Table-Insert не превосходит Зn, и учётную стоимость каждой такой операции можно считать равной 3.

Понять, откуда берётся коэффициент 3, можно с помощью метода предоплаты. Именно, при выполнении каждой операции Table-Insert(T,x) будем вносить по 3 доллара, при этом один доллар немедленно израсходуем на оплату операции "записать х в table[Т]", ещё один доллар прикрепим к элементу x, а оставшийся отдадим одному из элементов, уже записанных в таблицу (из тех, что ещё не получили своего доллара). Этими долларами будет оплачиваться перенос записей из старой таблицы в расширенную. При этом всякий раз, когда таблицу необходимо расширять, каждый из её элементов будет иметь по доллару.

В самом деле, пусть при предыдущем расширении таблица имела размер m и была расширена до 2m. С тех пор мы добавили m элементов, при этом и добавленные элементы, и каждый из m старых элементов получили по доллару. Таким образом, следующее расширение таблицы уже оплачено.

Можно проанализировать алгоритм Table-Insert и с помощью метода потенциалов. Чтобы это сделать, надо придумать такую потенциальную функцию, которая равна нулю сразу после расширения таблицы и нарастает по мере расширения таблицы (становясь равной размеру таблицы в тот момент, когда свободных ячеек не остаётся). Этим условиям удовлетворяет, например, функция

F(T) = 2num[T] − size[T]  (4)

Начальное значение потенциала равно нулю, и поскольку в любой момент не менее половины таблицы заполнено, значение F(T) всегда неотрицательно. Стало быть, сумма учётных стоимостей операций Table-Insert (определённых по методу потенциалов как фактическая стоимость плюс изменение потенциала) оценивает сверху суммарную фактическую стоимость.

Найдём учётные стоимости. Для этого обозначим через sizei, numi и Fi размер, количество записей и потенциал таблицы после i-й операции Table-Insert. Если эта операция не сопровождалась расширением таблицы, то sizei = sizei−1, numi = numi−1 + 1 и ci = 1, откуда

c*i = ci + Fi − Fi−1 = 3

Если же i-я операция Table-Insert сопровождалась расширением таблицы, то sizei⁄2 = sizei−1 = numi−1 и ci = numi, откуда опять-таки

c*i = ci + Fi − Fi−1 = numi + (2numi − sizei) − (2numi−1 − sizei−1) = numi + (2numi − (2numi − 2)) − (2(numi − 1) − (numi − 1)) = numi + 2 − (numi − 1) = 3

Далее изображена зависимость величин numi, sizei и Φi от i. Видно, что потенциал накапливается к моменту расширения таблицы.

зависимость величин от i

Размер таблицы (sizei), число записей (numi) и потенциал (Fi = 2numi − sizei) как функции от числа операций Table-Insert, обозначенного буквой i.

График num — красная линия, график size — зеленая линия, график F — фиолетовая.

Непосредственно перед расширением таблицы F возрастает до numi, чтобы оплатить это расширение. Сразу после расширения потенциал падает до нуля, но тут же и возрастает до 2 (за счёт добавления записи после расширения).

Расширение и сокращение таблицы

Теперь займёмся операцией Table-Delete (удалить из таблицы). Помимо удаления ненужной записи из таблицы, желательно сократить (contract) таблицу, как только коэффициент заполнения станет слишком низок. Общая стратегия тут та же, что и при расширении таблицы: как только число записей падает ниже некоторого предела, мы выделяем память под новую таблицу меньшего размера, копируем в меньшую таблицу все записи из большей, после чего возвращаем операционной системе память, занимавшуюся старой таблицей. Мы построим алгоритм Table-Delete со следующими свойствами:

  • коэффициент заполнения ограничен снизу положительной константой
  • учётная стоимость операций Table-Insert и Table-Delete есть O(1)

При этом мы по-прежнему будем считать, что стоимость алгоритма определяется количеством операций "записать в таблицу" и противоположных им операций "убрать из таблицы"; стоимость каждой из этих элементарных операций примем за единицу.

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

В самом деле, пусть n — натуральное число, являющееся степенью двойки. Предположим, что сначала мы добавили к пустой (не содержащей ячеек) таблице n⁄2 + 1 записей, а затем провели ещё n⁄2 − 1 операцию в такой последовательности: два удаления, затем два добавления, затем опять два удаления, опять два добавления, и т. д. После n⁄2 + 1 добавлений размер таблицы станет равным n (и заполнено будет чуть больше половины ячеек); после двух удалений его придётся сократить до n⁄2; после следующих двух добавлений размер опять возрастёт до n, после двух удалений — сократится до n⁄2, и т. д.

Стоимость каждого сокращения и расширения есть α(n), и количество сокращений и расширений также есть α(n), так что стоимость n операций есть α(n2), а средняя стоимость в расчёте на одну операцию оказывается равной α(n).

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

Дела пойдут лучше, если мы разрешим коэффициенту заполнения опускаться ниже 1⁄2. Именно, мы по-прежнему удваиваем размер таблицы при попытке добавить запись к заполненной таблице, а вот сокращение таблицы вдвое мы предпринимаем только тогда, когда коэффициент заполнения падает ниже 1⁄4. Таким образом, коэффициент заполнения всегда будет больше или равен 1⁄4. Другими словами, мы считаем 50% оптимальным коэффициентом заполнения таблицы, и возвращаемся к такой ситуации, как только коэффициент заполнения отклонится от оптимального в два раза (в любую сторону).

Для оценки стоимости последовательности из n операций Table-Insert и Table-Delete, применённых к пустой таблице, мы воспользуемся методом потенциалов. Потенциальная функция будет равна нулю, когда коэффициент заполнения оптимален (равен 1⁄2) — так будет сразу после сокращения или расширения. Потенциал возрастает по мере того, как коэффициент заполнения приближается к 1 или 1⁄4. Напомним, что коэффициент заполнения α(Т) равен num[T]⁄size[T], если size[T] ≠ 0, и равен 1, если size[T] (и тем самым num[Т]) равно нулю. Нашим требованиям удовлетворяет такая потенциальная функция:

F(T) = size[T]⁄2 − num[T], если α(Т) ≤ 1⁄2  (5.1)
F(T) = 2num[T] − size[T], если α(Т) ≥ 1⁄2  (5.2)

Заметим, что F(Т) = 0 при α(Т) = 1⁄2 (по любой из двух формул), что потенциал пустой таблицы равен нулю и что потенциал всегда неотрицателен. Если коэффициент заполнения равен 1 или 1⁄4, то F[T] = num[Т], так что накопленного потенциала достаточно для оплаты расширения или сокращения таблицы.

Ниже изображено изменение потенциала в процессе выполнения последовательности операций Table-Insert и Table-Delete.

Изменение потенциала в процессе выполнения последовательности операций Table-Insert и Table-Delete

Размер таблицы (sizei), число записей (numi) и потенциал

F(T) = size[T]⁄2 − num[T], если α(Т) ≤ 1⁄2
F(T) = 2num[T] − size[T], если α(Т) ≥ 1⁄2

как функции от числа операций Table-Insert и Table-Delete, обозначенного буквой i. График num — красная линия, график size — зеленая линия, график F — фиолетовая. Непосредственно перед расширением или сокращением таблицы потенциал равен количеству записей.

Найдём учётные стоимости операций при таком потенциале F. Если операция Table-Insert или Table-Delete не сопровождается расширением или сокращением таблицы, то изменение потенциала не превосходит 2 (size не меняется, num меняется на 1), так что учётная стоимость не превосходит 3. В случае расширения или сжатия таблицы учётная стоимость оказывается равной 1, так как изменения в потенциале компенсируют затраты на копирование.

Таким образом, учётная стоимость каждой из операций есть O(1), так что фактическая стоимость последовательности из n операций есть O(n).

Литература

  1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.

Визуализаторы

  1. Бреслав А., Воробьева Е. Методы амортизационного анализа (2003)
  2. Бреслав А., Воробьева Е. Визуализатор динамической таблицы (2003)

Елена Воробьева, Андрей Бреслав, Александр Кузнецов


Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий