Twierdzenie o rekurencji uniwersalnej

Twierdzenie o rekurencji uniwersalnej jest twierdzeniem matematycznym pozwalającym w łatwy sposób znajdować ograniczenie asymptotyczne pewnej klasy funkcji zdefiniowanych rekurencyjnie.

Twierdzenie o rekurencji uniwersalnej

Jeżeli funkcja $T(n),$ dla $a\geqslant 1,b>1,n>0$ i funkcji dodatniej $f$ jest zdefiniowana następująco:

$T(n)={\begin{cases}\Theta (1)&:1\leqslant n<b\\a\cdot T\left({\frac {n}{b}}\right)+f(n)&:n\geqslant b\end{cases}},$

to:

• jeżeli $f(n)=O(n^{\log _{b}a-\epsilon })$ dla pewnej stałej $\epsilon >0,$ to $T(n)=\Theta (n^{\log _{b}a}),$
• jeżeli $f(n)=\Theta (n^{\log _{b}a}),$ to $T(n)=\Theta (n^{\log _{b}a}\cdot \log n),$
• jeżeli $f(n)=\Omega (n^{\log _{b}a+\epsilon })$ dla pewnej stałej ε > 0 i jeżeli $a\cdot f\left({\frac {n}{b}}\right)\leqslant c\cdot f(n)$ dla pewnej stałej $c\in (0,1),$ dla dostatecznie dużych $n,$ to $T(n)=\Theta (f(n)).$

Tak zdefiniowane funkcje $T$ stanowią pewien schemat działania algorytmów typu „dziel i zwyciężaj” – problem o rozmiarze $n$ dzielony jest na $a$ podproblemów, każdy wielkości ${\frac {n}{b}},$ funkcja $f$ przedstawia koszt dzielenia problemu, oraz połączenia rozwiązań podproblemów.

Intuicyjna interpretacja

Każdy z trzech przypadków rekurencji uniwersalnej sprowadza się do stwierdzenia, która z funkcji $n^{\log _{b}a}$ i $f$ jest „większa”. Gdy znana jest odpowiedź na to pytanie, automatycznie znane jest asymptotyczne ograniczenie danej rekursji – jest nią owa „większa funkcja”.

„Dziury” rekurencji uniwersalnej

Należy zdawać sobie sprawę, że twierdzenie o rekurencji uniwersalnej nie wyczerpuje wszystkich przypadków, nawet rekursji „typu” $T\left({\frac {n}{b}}\right)+f(n)$ – pomiędzy przypadkami twierdzenia istnieją „dziury”. W pierwszym przypadku funkcja $f$ musi być wielomianowo mniejsza od $n^{\log _{b}a}.$ W trzecim przypadku oprócz wielomianowej większości wymagana jest pewna „regularność”, „gładkość” funkcji. Jeżeli funkcja $f$ należy do którejś z tych funkcji dla których nie ma „wielomianowej różnicy”, to twierdzenie o rekursji uniwersalnej nie pozwala znaleźć asymptotycznego oszacowania rekursji.

Dowód twierdzenia o rekurencji uniwersalnej

Dla n będących potęgą b

Niech $n$ będzie potęgą liczby rzeczywistej $b,$ takiej, że $b>1.$

Lemat 1

Niech zmienne $a,$ $b$ i funkcja $f$ będą zdefiniowane jak powyżej. Jeśli dla pewnej dodatniej liczby całkowitej $i$ funkcja $T$ jest zdefiniowana następująco:

$T(n)={\begin{cases}\Theta (1)&:n=1\\a\cdot T\left({\frac {n}{b}}\right)+f(n)&:n=b^{i}\end{cases}},$

to

$T(n)=\Theta (n^{\log _{b}a})+\sum _{j=0}^{\log _{b}n-1}a^{j}\cdot f\left({\frac {n}{b^{j}}}\right).\quad {}$ (*)

Dowód

Rozważmy drzewo rekursji funkcji $T$ zdefiniowanej jak wyżej.

• Koszt korzenia drzewa wynosi $f(n),$ a jego każdego z $a$ synów – $f\left({\frac {n}{b}}\right).$ Dla każdego syna korzenia koszt każdego z jego $a$ synów wynosi $f\left({\frac {n}{b^{2}}}\right).$ A więc istnieje dokładnie $a^{2}$ węzłów leżących w odległości 2 od korzenia.

• Ogólniej, dla $j<b$ istnieje $a^{j}$ węzłów o koszcie $f\left({\frac {n}{b^{j}}}\right)$ oddalonych od korzenia o odległość $j.$

• • Koszt każdego liścia wynosi $T(1)=\Theta (1),$ a ponieważ ${\frac {n}{b^{\log _{b}n}}}=1$ to każdy liść znajduje się na głębokości $\log _{b}n.$ Drzewo rekursji posiada $a^{\log _{b}n}=n^{\log _{b}a}$ liści.

Sumując koszty wszystkich poziomów drzewa otrzymamy równanie (*), ponieważ koszt wszystkich „poziomów” węzłów właściwych (tj. niebędących liśćmi) wynosi $\sum _{j=0}^{\log _{b}n-1}a^{j}\cdot f\left({\frac {n}{b^{j}}}\right)$ a koszt liści to $\Theta (n^{\log _{b}a}).$

Lemat 2

Niech $a,$ $b$ i $f$ będą określone jak powyżej. Jeżeli $g$ jest funkcją określoną dla $n$ będących potęgami $b$ w następujący sposób:

$g(n)=\sum _{j=0}^{\log _{b}n-1}a^{j}\cdot f\left({\frac {n}{b^{j}}}\right).$

To dla $n$ będących potęgami $b$ funkcję $g$ można oszacować:

• • jeżeli $f(n)=O(n^{\log _{b}a-\epsilon })$ dla pewnej stałej $\epsilon >0,$ to $g(n)=\Theta (n^{\log _{b}a}),$
  • jeżeli $f(n)=\Theta (n^{\log _{b}a}),$ to $g(n)=\Theta (n^{\log _{b}a}\cdot \log n),$
  • jeżeli $f(n)=\Omega (n^{\log _{b}a+\epsilon })$ dla pewnej stałej ε > 0 i jeżeli $a\cdot f\left({\frac {n}{b}}\right)\leqslant c\cdot f(n)$ dla pewnej stałej $c\in (0,1),$ dla dostatecznie dużych $n,$ to $g(n)=\Theta (f(n)).$

Dowód

Korzystając z oszacowania z lematu 2 dla sumy (*). Dla kolejnych przypadków z lematu 2 zachodzi:

• $T(n)=\Theta (n^{\log _{b}a})+O(n^{\log _{b}a})=\Theta (n^{\log _{b}a}),$

• $T(n)=\Theta (n^{\log _{b}a})+\Theta (n^{\log _{b}a}\cdot \log n)=\Theta (n^{\log _{b}a}\cdot \log n),$

• $T(n)=\Theta (n^{\log _{b}a})+\Theta (f(n))=\Theta (f(n)),$ ponieważ $f(n)=\Omega (n^{\log _{b}a+\epsilon }).$

Dla dowolnych n

Dla dowolnych $n$ (nie będących potęga $b$) wartość argumentu ${\frac {n}{b}}$ może oznaczać $\left\lfloor {\frac {n}{b}}\right\rfloor$ lub $\left\lceil {\frac {n}{b}}\right\rceil .$

Odpowiednio górne i dolne oszacowanie dla funkcji

$T(n)=a\cdot T\left(\left\lfloor {\frac {n}{b}}\right\rfloor \right)+f(n)\quad {}$ (1)

i

$T(n)=a\cdot T\left(\left\lceil {\frac {n}{b}}\right\rceil \right)+f(n)\quad {}$ (2)

jest banalne do znalezienia, przy wykorzystaniu własności $\left\lfloor {\frac {n}{b}}\right\rfloor \geqslant {\frac {n}{b}}$ i $\left\lceil {\frac {n}{b}}\right\rceil \leqslant {\frac {n}{b}}.$

Równanie rekurencyjne można oszacować z góry w następujący sposób:

Niech

$n[i]={\begin{cases}n&:i=0\\\left\lceil {\frac {n[i-1]}{b}}\right\rceil &:i>0\end{cases}}.$

Wtedy schodzenie w dół rekursji oznacza jej rekurencyjne wywoływanie kolejno dla argumentów $n[0],\ n[1],\ n[2],\dots$

$T(n)=T\left(\left\lceil {\frac {n}{b}}\right\rceil \right)=T\left(\left\lceil {\frac {\left\lceil {\frac {n}{b}}\right\rceil }{b}}\right\rceil \right)=\ldots$

Korzystając z nierówności $\left\lceil a\right\rceil \leqslant a+1,$ mamy:

• $n[0]\leqslant n,$
• $n[1]\leqslant {\frac {n}{b}}+1,$
• $n[2]\leqslant {\frac {n}{b^{2}}}+{\frac {1}{b}}+1,$
• $n[3]\leqslant {\frac {n}{b^{3}}}+{\frac {1}{b^{2}}}+{\frac {1}{b}}+1,$
• $\ldots$
• $n[i]\leqslant {\frac {n}{b^{i}}}+\sum _{k=0}^{i-1}{\frac {1}{b^{k}}}<{\frac {n}{b^{i}}}+\sum _{k=0}^{\infty }{\frac {1}{b^{k}}}={\frac {n}{b^{i}}}+{\frac {b}{b-1}}.$

Dla $i=\left\lfloor \log _{b}n\right\rfloor$

$n[i]=n[\left\lfloor \log _{b}n\right\rfloor ]<{\frac {n}{b^{\left\lfloor \log _{b}n\right\rfloor }}}+{\frac {b}{b-1}}\leqslant {\frac {n}{b^{\log _{b}n-1}}}+{\frac {b}{b-1}}={\frac {n}{\frac {n}{b}}}+{\frac {b}{b-1}}\in O(1).$

Oznacza to, że dla wywołań rekursji na poziomie co najmniej $n[\left\lfloor \log _{b}n\right\rfloor ]$ i większych, rozmiar problemu jest stały.