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

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

 

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

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

${\displaystyle T(x)=g(x)+\sum _{i=1}^{k}a_{i}T(b_{i}x+h_{i}(x))\;\;{\text{для }}x\geq x_{0},}$

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

• ${\displaystyle x_{0}={\text{const}}}$,

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

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

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

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

Замечание

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

Пример 1

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

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

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

${\displaystyle {\begin{aligned}T(x)&\in \Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}\,du\right)\right)=\\&=\Theta \left(x^{2}\left(1+\int _{1}^{x}{\frac {u^{2}}{u^{3}}}\,du\right)\right)=\\&=\Theta (x^{2}(1+\ln {(x)}))=\\&=\Theta (x^{2}\log {(x)}).\end{aligned}}}$

Пример 2

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

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

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

${\displaystyle {\begin{aligned}T(x)&\in \Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}\,du\right)\right)=\\&=\Theta \left(x\left(1+\int _{1}^{x}{\frac {u}{u^{2}}}\,du\right)\right)=\\&=\Theta (x(1+\ln {(x)}))=\\&=\Theta (x\log {(x)}).\end{aligned}}}$

Значение

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

См. также

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