Вводная

Классы функций, используемые для оценки сложности алгоритмов

Все функции, используемые ниже для оценки сложности алгоритмов, считаются асимптотически неотрицательными функциями натурального аргумента, то есть неотрицательными, начиная с некоторого значения аргумента $$n$$.

Для асимптотических оценок сверху используется класс функций$${ O (g(n))=\{f(n):\exists c>0, \exists n_{0} \forall n>n_{0} [0\le f(n)\le c\cdot g(n)]\}. }$$

Для асимптотических оценок снизу используется класс функций$${ \Omega (g(n))=\{ f(n):\exists c>0,\exists n_{0} \forall n>n_{0} [0\le c\cdot g(n)\le f(n)]\}. }$$

Для асимптотически точных оценок используется класс функций$${ \Theta (g(n))=\{ f(n):\exists c_{1},c_{2} >0,\exists n_{0} \forall n>n_{0} [0\le c_{1} g(n)\le f(n)\le c_{2} g(n)]\}. }$$

Очевидно, что справедливы следующие соотношения$${ \begin{gathered} \Theta (g(n))= O (g(n))\cap \Omega (g(n)),\\ f(n)\in O (g(n))\Leftrightarrow g(n)\in \Omega (f(n)). \end{gathered} }$$

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

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

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

Амортизационный анализ применяется при оценке времени выполнения корректной последовательности, состоящей из $$n$$ однотипных или разнотипных операций с некоторой структурой данных. Если верхнюю оценку времени выполнения одной операции умножить на $$n$$, получим верхнюю оценку выполнения всех $$n$$ операций. Часто такая оценка бывает сильно завышенной. Иногда длительное время выполнения очередной операции влечет за собой малое время выполнения следующих операций. Более того, такая ситуация может создаваться искусственно, то есть при выполнении очередной операции мы можем готовить почву для более эффективного выполнения следующей. Поэтому возникает задача изучения асимптотического поведения гарантированной оценки для среднего времени выполнения одной операции.

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

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

Метод группировки. Предположим, что мы оценили сверху время выполнения последовательности из $$n$$ операций, установив, что она не превосходит $$T(n)$$, тогда величину $$T(n)/n$$ объявим учетной стоимостью любой операции из рассматриваемой последовательности, независимо от ее длительности.

Метод предоплаты. В этом методе операции разных типов получают разные учетные стоимости, причем эти стоимости могут быть как больше, так и меньше фактических. Если учетная стоимость превосходит фактическую, то разность между ними рассматривается как резерв на оплату в будущем тех операций, у которых учетная стоимость ниже реальной. Учетные стоимости должны выбираться так, чтобы в любой момент времени фактическая стоимость не превосходила суммы учетных стоимостей, то есть чтобы резерв оставался неотрицательным.

Метод потенциалов. Этот метод является обобщением метода предоплаты. Здесь резерв определяется функцией состояния структуры данных в целом. Эта функция называется потенциалом.

Общая схема метода такова. Пусть над структурой данных предстоит произвести $$n$$ операций, и пусть $$D_i$$ — состояние структуры данных после $$i$$ -й операции ( $$D_0$$ — исходное состояние). Потенциал представляет собой функцию $$\phi$$ из множества возможных состояний структуры данных в множество действительных чисел.

Пусть $$c_i$$ — реальная стоимость $$i$$ -й операции. Учетной стоимостью $$i$$ -й операции объявим число $$C_i$$, определяемое формулой$$\eq*{ C_{i} =c_{i} +\phi (D_{i})-\phi (D_{i-1}) }$$ как сумма реальной стоимости операции плюс приращение потенциала в результате выполнения этой операции. Тогда суммарная учетная стоимость всех операций равна$$\eq*{ \suml_{i=1}^{n}C_{i} =\suml_{i=1}^{n}c_{i} +\phi (D_{n} )-\phi (D_{0}). }$$

Если нам удалось придумать функцию $$\phi$$, для которой$$\eq*{ \phi (D_{n} )\ge \phi (D_{0}), }$$ то суммарная учетная стоимость даст верхнюю оценку для реальной стоимости последовательности из $$n$$ операций. Не ограничивая общности, можно считать, что$$\eq*{ \phi (D_{0} )=0. }$$ Говоря неформально, если разность потенциалов$$\eq*{ \phi (D_{i} )-\phi (D_{i-1}) }$$ положительна, то учетная стоимость $$i$$ -й операции включает в себя резерв (предоплату за будущие операции); если же эта разность отрицательна, то учетная стоимость $$i$$ -й операции меньше реальной и разница покрывается за счет накопленного к этому моменту потенциала.

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

Ниже эти три метода будут проиллюстрированы на примере анализа работы двоичного счетчика с единственной операцией Increment (прибавление единицы).

Амортизационный анализ работы двоичного счетчика

Рассмотрим работу $$k$$ -разрядного двоичного сбрасываемого счетчика, реализованного как массив битов $$A[0 \ldots k-1]$$, хранящего двоичную запись числа $$x$$. Будем считать, что $$A[0]$$ — младший разряд. Пусть первоначально $$x = 0$$. Единственной операцией в нашем примере будет операция Increment, увеличивающая $$x$$ на 1 по модулю $$2^k$$.

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

Анализ работы двоичного счетчика методом группировки. Применим метод группировки для анализа сложности $$n$$ -кратного выполнения операции Increment. Поскольку в худшем случае, когда массив $$A$$ состоит из одних единиц, меняются все $$k$$ битов, то $$n$$ -кратное выполнение операции Increment может быть оценено как $$O(nk)$$ элементарных операций. Но эта оценка слишком груба.

Чтобы получить более точную оценку, учтем, что не каждый раз значения всех $$k$$ битов меняются. В самом деле, младший бит $$A[0]$$ меняется при каждом исполнении операции Increment. Следующий по старшинству бит $$A[1]$$ меняется только через раз. При счете от нуля до $$n$$ этот бит меняется $$[n/2]$$ раз. Бит $$A[2]$$ меняется только каждый четвертый раз, и так далее. Заметим, что если $$0 \le i \le \log_2 n$$, то в процессе счета от $$0$$ до $$n$$ разряд $$A[i]$$ меняется $$[n/2^i]$$ раз, а если $$i > [\log_2 n]$$, то он вообще не меняется. Следовательно, общее количество операций зануления и записи 1 равно$$\eq*{ n + [n/2] + [n/4] + \ldots + [n/2]^{[\log n]} < n(1 + 1/2 + 1/4 + \ldots) = 2n. }$$ Тем самым, увеличение двоичного счетчика от $$0$$ до $$n$$ требует не более $$O(n)$$ операций, причем константа не зависит от $$k$$ и равна $$2$$. Учетную стоимость операции Increment можно считать равной $$O(n)/n = O(1)$$.

Анализ работы двоичного счетчика методом предоплаты. Применим метод предоплаты для анализа сложности $$n$$ -кратного выполнения операции Increment. Будем считать, что реальная стоимость изменения бита составляет $$1$$ рубль. Установим такие учетные стоимости: $$2$$ рубля за запись единицы, $$0$$ за очистку. При каждой установке бита в единицу одним из двух рублей учетной стоимости будем расплачиваться за реальные затраты на эту установку, а второй рубль, остающийся в резерве, будем "прикреплять" к рассматриваемому биту. Поскольку первоначально все биты были нулевыми, в каждый момент к каждому ненулевому биту будет прикреплен резервный рубль. Стало быть, за очистку любого бита дополнительно платить нам не придется: мы расплатимся за нее рублем, прикрепленным к этому биту в момент его установки.

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

Анализ работы двоичного счетчика методом потенциалов. Проанализируем теперь трудоемкость $$n$$ -кратного выполнения операции Increment с помощью метода потенциалов.

Пусть $$D_0$$ — содержимое счетчика в начальный момент, $$D_i$$ — содержимое счетчика после выполнения $$i$$ -й операции, $$\phi(D_i)$$ — число единиц в записи $$D_i$$, $$t_i$$ — число единиц, превращенных в нули при $$i$$ -й операции. Очевидно, что$$\eq*{ \phi(D_i) \le \phi(D_{i-1}) - t_i +1. }$$

Пусть далее $$c_i$$ — реальная стоимость $$i$$ -й операции Increment, $$C_i$$ — ее учетная стоимость. Очевидно, что $$c_i \le t_i + 1$$. Тогда$$C_{i} =c_{i} +\phi (D_{i})-\phi (D_{i-1} )\le t_{i} +1+\phi (D_{i} )-\phi (D_{i-1} )\le \\ \le t_{i} +1+\phi (D_{i-1})-t_{i} +1-\phi (D_{i-1})=2.$$

Если счет начинается с нуля, то

и

для всех $$i$$. Поскольку сумма учетных стоимостей оценивает сверху сумму реальных стоимостей, имеем

то есть получаем, что суммарная стоимость $$n$$ операций есть $$O(n)$$ с константой (двойкой), не зависящей от $$k$$.

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

откуда при достаточно больших значениях $$n$$ ( $$n = \Om(k)$$ ) получаем, что реальная стоимость оценивается как $$O(n)$$, причем константа в $$O$$ -записи не зависит ни от $$k$$, ни от начального значения счетчика.