Теорема Акра-Баззи

 

В информатике и теории вычислимости метод Акра–Баззи, или теорема Акра–Баззи, используется для исследования асимптотического поведения рекуррентных функций, которые возникают при анализе алгоритмов типа «разделяй и властвуй», где подзадачи имеют существенно разные размеры. Данный метод является обобщением основной теоремы о рекуррентных соотношениях, которая предполагает, что подзадачи на каждом уровне рекурсии имеют одинаковый размер. Теорема названа в честь математиков Мохамада Акры и Луая Баззи.

Формулировка

Метод Акра–Баззи применяется к рекуррентным формулам вида:

$T(x)=g(x)+\sum _{i=1}^k{a}_{i}T(b_{i}x+h_i(x))\text{для }x\ge x_0,$

для которых выполнено:

• $x_0=\text{const}$,

• при малых $x$ искомая рекуррента $T(x)=\text{const}=O(1)$, где $O$ обозначает нотацию $O$-большое,
• $a_i$ и $b_i$ являются константами $\mathrm{\forall }i\in \overline{1,k}$,
• $a_i>0$ $\mathrm{\forall }i\in \overline{1,k}$,
• $0<b_i<1$ $\mathrm{\forall }i\in \overline{1,k}$,
• $|g^{\prime }(x)|\in O(x^c)$, где $c$ - константа,
• $|h_i(x)|\in O\left(\frac{x}{(\log x{)}^2}\right)$ $\mathrm{\forall }i\in \overline{1,k}$.

Асимптотическое поведение рекурренты $T(x)$ находится путем определения значения $p$ для которого $\sum _{i=1}^k{a}_i{b}_i^p=1$ и последующей подстановкой этого значения в выражение:

$T(x)\in \mathrm{\Theta }\left(x^p(1+\underset{1}{\overset{x}{\int }}\frac{g(u)}{u^{p+1}}du)\right).$

Под $\mathrm{\Theta }$ здесь имеется в виду одновременное выполнение условий $O$-большое (ограниченность сверху) и $\mathrm{\Omega }$ (ограниченность снизу).

Замечание

Отметим, что функции $h_i(x)$ можно рассматривать как небольшие возмущения в аргументах рекурренты $T$. Учитывая, что $\lfloor b_{i}x\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)$ и что абсолютная величина $\lfloor b_{i}x\rfloor -b_{i}x$ всегда находится в интервале между 0 и 1, можно использовать добавки $h_i(x)$ для исключения взятия целой части аргумента. К примеру, рекуррентные формулы $T(n)=n+T\left(\frac{1}{2}n\right)$ и $T(n)=n+T\left(\lfloor \frac{1}{2}n\rfloor \right)$ будут, согласно теореме Акра–Баззи, иметь одинаковое асимптотическое поведение.

Пример 1

Пусть $T(n)$ задаётся системой:

$\{\begin{array}{c}T(n)=1,\text{для}0\le n\le 3,\\ T(n)=n^2+\frac{7}{4}T\left(\lfloor \frac{1}{2}n\rfloor \right)+T\left(\lceil \frac{3}{4}n\rceil \right),\text{для}n>3.\end{array}$

Применим метод Акра-Баззи для поиска асимптотики на $T(n)$, так как все условия теоремы выполнены. Сначала необходимо найти значение $p$, решив уравнение $\frac{7}{4}{\left(\frac{1}{2}\right)}^p+{\left(\frac{3}{4}\right)}^p=1$. В данном примере $p=2$. Далее, используя формулу Акра-Баззи, можно определить асимптотическое поведение следующим образом:

$\begin{array}{cc}T(x)& \in \mathrm{\Theta }\left(x^p(1+\underset{1}{\overset{x}{\int }}\frac{g(u)}{u^{p+1}}du)\right)=\\ & =\mathrm{\Theta }\left(x^2(1+\underset{1}{\overset{x}{\int }}\frac{u^2}{u^3}du)\right)=\\ & =\mathrm{\Theta }(x^2(1+\ln (x)))=\\ & =\mathrm{\Theta }(x^2\log (x)).\end{array}$

Пример 2

Рассмотрим в качестве примера алгоритм классической сортировки слиянием. На каждом уровне рекурсии функция сортировки вызывает себя дважды на половинных наборах входных данных и выполняет слияние подмассивов, производя в худшем случае $n-1$ сравнение. Таким образом, рекуррентная формула для сортировки слиянием даётся системой:

$\{\begin{array}{c}T(0)=0,\\ T(n)=T\left(\lfloor \frac{1}{2}n\rfloor \right)+T\left(\lceil \frac{1}{2}n\rceil \right)+n-1,\text{для}n\in \mathbb{N}.\end{array}$

Применим метод Акра-Баззи для поиска асимптотики на $T(n)$, так как все условия теоремы выполнены. Сначала необходимо найти значение $p$, решив уравнение ${\left(\frac{1}{2}\right)}^p+{\left(\frac{1}{2}\right)}^p=1$. В данном примере $p=1$. Далее, используя формулу Акра-Баззи, можно определить асимптотическое поведение следующим образом:

$\begin{array}{cc}T(x)& \in \mathrm{\Theta }\left(x^p(1+\underset{1}{\overset{x}{\int }}\frac{g(u)}{u^{p+1}}du)\right)=\\ & =\mathrm{\Theta }\left(x(1+\underset{1}{\overset{x}{\int }}\frac{u}{u^2}du)\right)=\\ & =\mathrm{\Theta }(x(1+\ln (x)))=\\ & =\mathrm{\Theta }(x\log (x)).\end{array}$

Значение

Метод Акра–Баззи эффективнее большинства других методов определения асимптотического поведения, поскольку он технически удобен и охватывает очень широкий класс задач. В основном данный метод применяется для оценки времени выполнения алгоритмов типа «разделяй и властвуй».

Смотреть также

• Основная теорема о рекуррентных соотношениях
• Асимптотическая сложность

Внешние ссылки

• O Método de Akra-Bazzi na Resolução de Equações de Recorrência Шаблон:In lang