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 ${\displaystyle T(n),}$ dla ${\displaystyle a\geqslant 1,b>1,n>0}$ i funkcji dodatniej ${\displaystyle f,}$ jest zdefiniowana następująco:

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

Tak zdefiniowane funkcje T stanowią pewien schemat działania algorytmów typu „dziel i zwyciężaj” – problem o rozmiarze ${\displaystyle n}$ dzielony jest na ${\displaystyle a}$ podproblemów, każdy wielkości ${\displaystyle {\frac {n}{b}},}$ funkcja ${\displaystyle 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 ${\displaystyle 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” ${\displaystyle T\left({\frac {n}{b}}\right)+f(n)}$ – pomiędzy przypadkami twierdzenia istnieją „dziury”. W pierwszym przypadku funkcja f musi być wielomianowo mniejsza od ${\displaystyle 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 ${\displaystyle 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:

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

to

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

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 – ${\displaystyle f\left({\frac {n}{b}}\right).}$ Dla każdego syna korzenia koszt każdego z jego a synów wynosi ${\displaystyle f\left({\frac {n}{b^{2}}}\right).}$ A więc istnieje dokładnie ${\displaystyle a^{2}}$ węzłów leżących w odległości 2 od korzenia.

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

• • Koszt każdego liścia wynosi ${\displaystyle T(1)=\Theta (1),}$ a ponieważ ${\displaystyle {\frac {n}{b^{\log _{b}n}}}=1}$ to każdy liść znajduje się na głębokości ${\displaystyle \log _{b}n.}$ Drzewo rekursji posiada ${\displaystyle 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 ${\displaystyle \sum _{j=0}^{\log _{b}n-1}a^{j}\cdot f\left({\frac {n}{b^{j}}}\right)}$ a koszt liści to ${\displaystyle \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:

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

Dowód

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

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

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

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

Dla dowolnych n

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

Odpowiednio górne i dolne oszacowanie dla funkcji

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

i

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

jest banalne do znalezienia, przy wykorzystaniu własności ${\displaystyle \left\lfloor {\frac {n}{b}}\right\rfloor \geqslant {\frac {n}{b}}}$ i ${\displaystyle \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

${\displaystyle 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 ${\displaystyle n[0],\ n[1],\ n[2],\dots }$

${\displaystyle 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)=\cdots }$

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

• ${\displaystyle n[0]\leqslant n}$
• ${\displaystyle n[1]\leqslant {\frac {n}{b}}+1}$
• ${\displaystyle n[2]\leqslant {\frac {n}{b^{2}}}+{\frac {1}{b}}+1}$
• ${\displaystyle n[3]\leqslant {\frac {n}{b^{3}}}+{\frac {1}{b^{2}}}+{\frac {1}{b}}+1}$
• ${\displaystyle \cdots }$
• ${\displaystyle 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 ${\displaystyle i=\left\lfloor \log _{b}n\right\rfloor }$

${\displaystyle 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 ${\displaystyle n[\left\lfloor \log _{b}n\right\rfloor ]}$ i większych rozmiar problemu jest stały.