статье Уитни [200].

Задачами этой главы занимались многие авторы - Гаврил [80] (задача о выборе заявок), Лоулер [132], Горовиц и Сахни [105], Брассар и Братли [33] (задача о расписании).

Коды Хаффмена были изобретены в 1952 году [107]. Обзор методов сжатия информации (по состоянию на 1987 год) дали Лелевер и Хиршберг [136].

Корте и Ловас [127, 128, 129, 130] создали теорию гридоидов (greedoids), являющуюся обобщением теории, изложенной в разделе 17.4.

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

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

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

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

В разделе 18.2 рассказывается о методе предоплаты. При этом методе амортизационного анализа различным операциям могут присваиваться различные учётные стоимости. У некоторых опера-

ций учётная стоимость объявляется выше реальной. Когда выполняется такая операция, остаётся резерв, который считается хранящимся в определенном месте структуры данных. Этот резерв используется для доплаты за операции, учётная стоимость которых ниже фактической.

В методе потенциалов, обсуждаемом в разделе 18.3, резерв не связывается с какими-то конкретными объектами, а является функцией текущего состояния структуры данных. Эта функция называется «потенциалом», и учётные стоимости должны быть с ней согласованы.

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

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

Идеи, связанные с амортизационным анализом, полезно иметь в виду при разработке алгоритмов. Пример такого рода дан в разделе 18.4 (таблица переменного размера).

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

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

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

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

Push ж) добавляет элемент ж к стеку S;

Pop(5*) удаляет вершину стека S (и возвращает её).

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

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