В информатике и теории вычислимости метод Акра–Баззи , или теорема Акра–Баззи , используется для исследования асимптотического поведения рекуррентных функций , которые возникают при анализе алгоритмов типа «разделяй и властвуй» , где подзадачи имеют существенно разные размеры. Данный метод является обобщением основной теоремы о рекуррентных соотношениях , которая предполагает, что подзадачи на каждом уровне рекурсии имеют одинаковый размер. Теорема названа в честь математиков Мохамада Акры и Луая Баззи .
Метод Акра–Баззи применяется к рекуррентным формулам вида: [ 1]
T
(
x
)
=
g
(
x
)
+
∑
i
=
1
k
a
i
T
(
b
i
x
+
h
i
(
x
)
)
для
x
≥
x
0
,
{\displaystyle T(x)=g(x)+\sum _{i=1}^{k}a_{i}T(b_{i}x+h_{i}(x))\;\;{\text{для }}x\geq x_{0},}
для которых выполнено:
x
0
=
const
{\displaystyle x_{0}={\text{const}}}
при малых
x
{\displaystyle x}
T
(
x
)
=
const
=
O
(
1
)
{\displaystyle T(x)={\text{const}}=O(1)}
O
{\displaystyle O}
нотацию
O
{\displaystyle O}
-большое ,
a
i
{\displaystyle a_{i}}
b
i
{\displaystyle b_{i}}
∀
i
∈
1
,
k
¯
{\displaystyle \forall i\in {\overline {1,k}}}
a
i
>
0
{\displaystyle a_{i}>0}
∀
i
∈
1
,
k
¯
{\displaystyle \forall i\in {\overline {1,k}}}
0
<
b
i
<
1
{\displaystyle 0<b_{i}<1}
∀
i
∈
1
,
k
¯
{\displaystyle \forall i\in {\overline {1,k}}}
|
g
′
(
x
)
|
∈
O
(
x
c
)
{\displaystyle \left|g'(x)\right|\in O(x^{c})}
c
{\displaystyle c}
|
h
i
(
x
)
|
∈
O
(
x
(
log
x
)
2
)
{\displaystyle \left|h_{i}(x)\right|\in O\left({\frac {x}{(\log x)^{2}}}\right)}
∀
i
∈
1
,
k
¯
{\displaystyle \forall i\in {\overline {1,k}}}
Асимптотическое поведение рекурренты
T
(
x
)
{\displaystyle T(x)}
p
{\displaystyle p}
∑
i
=
1
k
a
i
b
i
p
=
1
{\displaystyle \sum _{i=1}^{k}a_{i}b_{i}^{p}=1}
[ 2]
T
(
x
)
∈
Θ
(
x
p
(
1
+
∫
1
x
g
(
u
)
u
p
+
1
d
u
)
)
.
{\displaystyle T(x)\in \Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}du\right)\right).}
Под
Θ
{\displaystyle \Theta }
O
{\displaystyle O}
Ω
{\displaystyle \Omega }
Отметим, что функции
h
i
(
x
)
{\displaystyle h_{i}(x)}
T
{\displaystyle T}
⌊
b
i
x
⌋
=
b
i
x
+
(
⌊
b
i
x
⌋
−
b
i
x
)
{\displaystyle \lfloor b_{i}x\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)}
⌊
b
i
x
⌋
−
b
i
x
{\displaystyle \lfloor b_{i}x\rfloor -b_{i}x}
h
i
(
x
)
{\displaystyle h_{i}(x)}
взятия целой части аргумента. К примеру, рекуррентные формулы
T
(
n
)
=
n
+
T
(
1
2
n
)
{\displaystyle T(n)=n+T\left({\frac {1}{2}}n\right)}
T
(
n
)
=
n
+
T
(
⌊
1
2
n
⌋
)
{\displaystyle T(n)=n+T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)}
Пусть
T
(
n
)
{\displaystyle T(n)}
{
T
(
n
)
=
1
,
для
0
≤
n
≤
3
,
T
(
n
)
=
n
2
+
7
4
T
(
⌊
1
2
n
⌋
)
+
T
(
⌈
3
4
n
⌉
)
,
для
n
>
3.
{\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}}}
Применим метод Акра-Баззи для поиска асимптотики на
T
(
n
)
{\displaystyle T(n)}
p
{\displaystyle p}
7
4
(
1
2
)
p
+
(
3
4
)
p
=
1
{\displaystyle {\frac {7}{4}}\left({\frac {1}{2}}\right)^{p}+\left({\frac {3}{4}}\right)^{p}=1}
p
=
2
{\displaystyle p=2}
T
(
x
)
∈
Θ
(
x
p
(
1
+
∫
1
x
g
(
u
)
u
p
+
1
d
u
)
)
=
=
Θ
(
x
2
(
1
+
∫
1
x
u
2
u
3
d
u
)
)
=
=
Θ
(
x
2
(
1
+
ln
(
x
)
)
)
=
=
Θ
(
x
2
log
(
x
)
)
.
{\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}}}
Рассмотрим в качестве примера алгоритм классической сортировки слиянием . На каждом уровне рекурсии функция сортировки вызывает себя дважды на половинных наборах входных данных и выполняет слияние подмассивов, производя в худшем случае
n
−
1
{\displaystyle n-1}
[ 3]
{
T
(
0
)
=
0
,
T
(
n
)
=
T
(
⌊
1
2
n
⌋
)
+
T
(
⌈
1
2
n
⌉
)
+
n
−
1
,
для
n
∈
N
.
{\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}}}
Применим метод Акра-Баззи для поиска асимптотики на
T
(
n
)
{\displaystyle T(n)}
p
{\displaystyle p}
(
1
2
)
p
+
(
1
2
)
p
=
1
{\displaystyle \left({\frac {1}{2}}\right)^{p}+\left({\frac {1}{2}}\right)^{p}=1}
p
=
1
{\displaystyle p=1}
T
(
x
)
∈
Θ
(
x
p
(
1
+
∫
1
x
g
(
u
)
u
p
+
1
d
u
)
)
=
=
Θ
(
x
(
1
+
∫
1
x
u
u
2
d
u
)
)
=
=
Θ
(
x
(
1
+
ln
(
x
)
)
)
=
=
Θ
(
x
log
(
x
)
)
.
{\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}}}
Метод Акра–Баззи эффективнее большинства других методов определения асимптотического поведения, поскольку он технически удобен и охватывает очень широкий класс задач. В основном данный метод применяется для оценки времени выполнения алгоритмов типа «разделяй и властвуй».
↑ Akra, Mohamad; Bazzi, Louay (May 1998). "On the solution of linear recurrence equations". Computational Optimization and Applications . 10 (2): 195—210. doi :10.1023/A:1018373005182 . S2CID 7110614 . ↑ Proof and application on few examples (неопр.) .↑ Introduction to algorithms / Thomas H. Cormen. — 3rd ed. — Cambridge, Mass: MIT Press, 2009. — 1292 с. — ISBN 978-0-262-03384-8 , 978-0-262-53305-8.
