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

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

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

Ф(Д-) £ 0 = Ф(А,).

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

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

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

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

Найдем учётную стоимость операции Increment. Пусть Ьг- - количество единиц в счетчике после г-й операции, и пусть г-я операция Increment очищает £г- битов; тогда Ьг- 6г 1 - £г- + 1 (кроме очистки битов, Increment может ещё установить в единицу не более одного бита). Стало быть, реальная стоимость г-ro Increment не превосходит ti + 1, а его учетная стоимость есть

Сг (U + 1) + (6,- - 6,- i) 2.

Если отсчёт начинается с нуля, то Ф(-Оо) = 0, так что Ф(ГЛ) Ф(-Со) для всех г, сумма учётных стоимостей оценивает сверху сумму реальных стоимостей, и суммарная стоимость п операций Increment есть 0(п) с константой (двойкой), не зависящей от к (размера счётчика).

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

пп

J> = с,--Ф(£)п) + Ф(Д),(18.3)

8 = 18 = 1

откуда, принимая во внимание, что сг- 2 для всех г, получаем, что

п

Усг <2п-Ъп + Ь0.

8 = 1

Поскольку бо к, для достаточно длинных последовательностей операций (га = £7(/г) операций Increment) реальная стоимость оценивается как О (га), причём константа в О-записи не зависит ни от к, ни от начального значения счетчика.

Упражнения

18.3-1 Пусть потенциальная функция Ф такова, что Ф(-Ог) Ф(.Оо) Для всех г, но Ф(-Оо) ф 0. Покажите, что существует потенциальная фуНКЦИЯ Ф, для которой Ф( Оо) = 0, Ф(-Ог) 0 для всех г, и учётные стоимости, рассчитанные с помощью функции Ф, совпадают с учётными стоимостями, рассчитанными с помощью Ф.

18.3-2 Сделайте упражнение 18-1.3 с помощью метода потенциалов.

18.3-3 Пусть наша структура данных - двоичная куча с операциями Insert и Extract-Min, работающими за время O(lgra) в худшем случае, где га - количество элементов. Придумайте потенциальную функцию Ф, для которой учётная стоимость операции Insert есть О (lgra), учётная стоимость операции Extract-Min есть 0(1), и сумма учётных стоимостей последовательности операций оценивает сверху реальную стоимость последовательности операций.

18.3-4 Пусть последовательность из га операций Push, Pop и Multipop применяется к стеку, содержащему so элементов, и приводит к стеку, содержащему sn элементов. Какова суммарная фактическая стоимость этих операций?

18.3-5 Пусть в начальном состоянии двоичный счетчик содержит Ь единиц, и пусть га = Q(b). Докажите, что стоимость га операций Increment есть О (га) с константой, не зависящей от Ь.

18.3-6 Как реализовать очередь на базе двух стеков (упражнение 11.1-6) таким образом, чтобы учетная стоимость операций Enqueue и Dequeue была 0(1)?

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

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

Будем считать, что динамическая таблица поддерживает операции Table-Insert (добавить к таблице) и Table-Delete (удалить из таблицы). При добавлении записи к таблице мы занимаем в таблице одну ячейку (slot), при удалении записи одна ячейка освобождается. Как конкретно реализованы сама таблица и эти операции, нас в данный момент не интересует: это может быть стек (раздел 11.1), куча (раздел 7.1), хеш-таблица (глава 12), или, наконец, массив или набор массивов (раздел 11.3).

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

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

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