Dowód twierdzenia o rekurencji uniwersalnej

Czyli odrobina hardkoru na podstawie Cormena i moich własnych rozważań nad istotą tego świata.
Jako że za niedługo pojawi się zapewne strona nt. techniki "divide et impera" (w szczególności zadania W), zamierzam ubiec jej autora z tym oto referatem zawierającym dowód twierdzenia podanego na lekcji. Ale o co właściwie chodzi?

Twierdzenie

Założenie

Dany jest algorytm, który dzieli problem na $a$ $b$-tych części, a do ich scalania używa procedury działającej w czasie $f(n)$. Oznaczmy jego czas działa nią przez funkcję $T(n)$. Czyli:

(1)

\begin{align} T(n) = aT\left(\frac{n}{b}\right) + f(n) \end{align}

Gdzie $n \in \mathbb{R}, a,b \in \mathbb{Z_{+}}$, a ułamek zaokrąglamy do podłogi albo sufitu.

Teza

1. $f(n)=O(n^{\log_{b}a-q}) \Rightarrow T(n)=\Theta(n^{\log_{b}a})$
2. $f(n)=\Theta(n^{\log_{b}a}) \Rightarrow T(n)=\Theta(n^{\log_{b}a}\log n)$
3. $f(n)=\Omega(n^{\log_{b}a+q}) \Rightarrow T(n)=\Theta(f(n))$, przy czym ten przypadek jest obostrzony warunkiem, że istnieje taka stała $0<c<1$, że dla dostatecznie dużych n $af\left(\frac{n}{b}\right)\leqslant cf(n)$, co jest dość logiczne dla funkcji wielomianowych, które rozpatrujemy: jako że b jest całkowite dodatnie, to po lewej stronie dzielimy przez b do potęgi zawartej w funkcji $f$, a po prawej zawsze przez $\frac{1}{c}>1$ do pierwszej, czyli przez większą liczbę, a więc w rozsądnych przypadkach otrzymamy liczbę mniejszą. Z tego punktu widzenia ten warunek jest idiotycznie trywialny, ale inaczej twierdzenie nie zadziała.

Obecne w tezie $q$ jest dodatnią stałą.

Przykład działania: Karatsuba

Cokolwiek by nie robił, dzieli on problem na trzy podproblemy operujące na połówkach danych, których rozwiązania potem scala w czasie $\Theta(n).$. Mamy więc $T(n) = 3T\left(\frac{n}{2}\right) + \Theta (n)$. Oczywiście $\Theta (n)=O(n^{\log_{2}3-q})$ (bo $\log_{2}3 > 1$, a więc mamy przypadek 1, czyli $T(n)=\Theta(n^{\log_{2}3-q})$.
++Żeby było jasne:

1. intuicyjnie, $\Theta$ to "asymptotycznie =", $O$ to "asymptotycznie <", zaś $\Omega$ to "asymptotycznie >", na przykład $2n^{2}= \Theta(n^{2}), 2n^{2}= O(n^{3}), 2n^{2}= \Omega(n).$
2. Będę korzystał z definicji logarytmu, czyli równości $a^{log_{a}b}=b$, oraz z własności $a^{\log_{b}n} = n^{\log_{b}a}$

Dowód

Prawie dowód

Dowiedziemy na razie prawdziwość naszego twierdzenia dla n będących dokładnie równe $b^{k}$ dla pewnego dodatniego k. W ty,m celu zmienimy też definicje asymptotycznych oszacowań ($O, \Theta , \Omega$) tak żeby szacowały tylko potęgi b.
Intuicyjnie widać, że jeżeli będzie działało dla takich n, to dla reszty też będzie działało, no bo niby z jakiej racji czas ma dla n z jakiegoś przedziału wystrzelić w górę, podczas gdy dla reszty rośnie rozsądnie…

No ale do rzeczy. Narysujemy sobie drzewo rekursji, przy czym (jedynie dla ustalenia uwagi) przyjmujemy, że koszt $f(n)$ jest kosztem po prostu związanym z konkretnym elementem tego drzewa, nieważne, czy go wydatkujemy przy scaleniu (MergeSort, Karatsuba), czy przy rozdzielaniu (nie wiem, czy takie algorytmy istnieją, musiałyby scalać w czasie stałym…). Drzewo to wygląda tak, że w korzeniu jest cały problem, a jego dzieci to podproblemy, na które go dzielimy.
A więc z korzeniem jest związany "pełny" koszt $f(n)$, z każdym z jego a dzieci - koszt $f(\frac{n}{b})$, i tak dalej… Ogólnie, jak widać, każdy element niebędący liściem dzielimy na a b-tych części, czyli każdy ma a dzieci o koszcie b razy mniejszym (tego zdania prosimy nie czytać publicznie). A więc element na j-tym poziomie (gdzie korzeń to poziom zerowy) ma koszt:

(2)

\begin{align} f\left(\frac{n}{b^{j}}\right) \end{align}

Ponieważ przejście do niższego o 1 poziomu polega na dzieleniu przez b, to poziomów w drzewie jest:

(3)

\begin{align} \log_{b}n + 1 \end{align}

(od numeru $0$ do $\log_{b} n$). Tu właśnie przydaje się założenie, że n jest potęgą b, inaczej liczba poziomów nie byłaby naturalna, a takie drzewo trudno by było narysować…
Na każdym poziomie znajduje się tyle elementów, ile było na poprzednim, razy a, bowiem każdy z nich został podzielony na a części. Ponieważ na zerowym poziomie jest jeden , to na j-tym poziomie jest elementów:

(4)

\begin{equation} a^{j} \end{equation}

A więc koszt wszystkich scalań, tzn koszt związany ze wszystkimi węzłami wynosi:

(5)

\begin{align} \sum_{j=0}^{log_{b}n - 1} a^{j}f\left(\frac{n}{b^{j}}\right) \end{align}

No dobra, rozpatrzyliśmy sobie wszystkie scalania, ale przecież same liście też coś kosztują. Jak już policzyliśmy, koszt liścia wynosi $f\left(\frac{n}{b^{\log_{b}n}}\right) = f(1)= \Theta(1)$. Liści jest, co też już mamy policzone, $a^{\log_{b}n}$, a więc do naszej sumy należy jeszcze dorzucić sumę kosztów liści, czyli $\Theta(a^{\log_{b}n}) = \Theta(n^{\log_{b}a})$. Podsumowując nasze dotychczasowe rozważania, mamy, że:

(6)

\begin{align} T(n)= \Theta(n^{\log_{b}a}) + \sum_{j=0}^{log_{b}n - 1} a^{j}f\left(\frac{n}{b^{j}}\right) \end{align}

Dla wszystkich trzech przypadków.
No to wstawmy $f(n)=O(n^{\log_{b}a-q})$, gdzie q jest nieujemną liczbą rzeczywistą. Oszacujmy sobie naszą sumę (5). Mamy:

(7)

\begin{align} \sum_{j=0}^{log_{b}n - 1} a^{j}f\left(\frac{n}{b^{j}}\right) = O\left(\sum_{j=0}^{log_{b}n - 1} a^{j}\left(\frac{n}{b^{j}}\right)^{\log_{b}a-q} \right) \end{align}

Teraz nadszedł czas na skorzystanie z naszej wiedzy kiełbasianej:

(8)

\begin{align} \sum_{j=0}^{\log_{b}n - 1} a^{j}\left(\frac{n}{b^{j}}\right)^{\log_{b}a-q} = n^{\log_{b}a-q} \sum_{j=0}^{\log_{b}n - 1} \left(\frac{a}{b^{\log_{b}a-q}}\right)^{j} = n^{\log_b}a-q \sum_{j=0}^{log_{b}n - 1} \left(\frac{ab^{q}}{b^{\log_{b}a}}\right)^{j} = \end{align}

(9)

\begin{align} =n^{\log_{b}a-q} \sum_{j=0}^{\log_{b}n - 1} \left(\frac{ab^{q}}{a}\right)^{j} = n^{\log_{b}a-q} \sum_{j=0}^{\log_{b}n - 1} \left(b^{q}\right)^{j} \end{align}

Jeżeli q=0, to mamy przypadek 2 z tezy. Wtedy powyższe wynosi:

(10)

\begin{align} n^{log_{b}a} \sum_{j=0}^{\log_{b}n - 1} \left(1\right)^{j} = n^{\log_{b}a} \log_{b}n = \Theta(n^{\log_{b}a} \log n) \overset{\underset{\mathrm{(6)}}{}}{\Rightarrow} T(n) = \Theta(n^{\log_{b}a}) + \Theta(n^{\log_{b}a}\log n) = \Theta(n^{\log_{b}a}\log n) \end{align}

Co kończy dowód przypadku 2.

Jeżeli zaś q jest dodatnie, wtedy mamy przypadek 1.wtedy suma w powyższym wyrażeni jest sumą $\log_{b}n$ kolejnych wyrazów ciągu geometrycznego (ach, kochamy to sformułowanie), a więc całe wyrażenie przyjmuje postać:

(11)

\begin{align} n^{\log_{b}a-q} \left(\frac{\left(b^{q}\right)^{\log_{b}n}-1}{b^{q}-1}\right) = n^{\log_{b}a-q} \left(\frac{\left(b^{\log_{b}n}\right)^{q}-1}{b^{q}-1}\right) = n^{\log_{b}a-q} \left(\frac{n^{q}-1}{b^{q}-1}\right) = n^{\log_{b}a-q} O(n^{q}) = O(n^{\log_{b}a}) \end{align}

A więc, na mocy (6), również mamy:

(12)

\begin{align} T(n) = \Theta(n^{\log_{b}a}) + O(n^{\log_{b}a}) = \Theta(n^{\log_{b}a}) \end{align}

Co z kolei kończy dowód przypadku 1.

Przypadek trzeci jest ciekawszy. Najpierw skorzystamy z własności zawartej w założeniu, czyli: $f\left(\frac{n}{b}\right)\leqslant \frac{c}{a}f(n)$ dla n będącego dowolną potęgą b . Ale dla j-tego poziomu mamy z niej, że:

(13)

\begin{align} f\left(\frac{n}{b^{j}}\right) \leqslant \frac{c}{a}f(\frac{n}{b^{j-1}}) \leqslant \left(\frac{c}{a}\right)^{2}f(\frac{n}{b^{j-2}}) \leqslant \dots \leqslant \left(\frac{c}{a}\right)^{j-1}f(\frac{n}{b}) \leqslant \left(\frac{c}{a}\right)^{j}f(n) \end{align}

Pamiętając że $0<c<1$, podstawimy to do sumy (5). A więc mamy:

(14)

\begin{align} \sum_{j=0}^{\log_{b}n - 1} a^{j}f\left(\frac{n}{b^{j}}\right) \leqslant \sum_{j=0}^{\log_{b}n - 1} c^{j}f\left(n\right) \end{align}

Co jest… sumą kolejnych wyrazów ciągu geometrycznego! Wyrazy te są dodatnie, więc wraz z dodawaniem kolejnych ta suma będzie się zwiększać. Można przeto oszacować ją przez sumę nieskończonego ciągu (bo $0<c<1$), a zatem przez wyrażenie:

(15)

\begin{align} \sum_{j=0}^{\log_{b}n - 1} c^{j}f\left(n\right) \leqslant f(n)\left( \frac{1}{1-c} \right) = O(f(n)) \end{align}

Czyli mamy pół sukcesu, bo oszacowaliśmy sobie tą sumę z dołu. Ale przyjrzyjmy się sumie (5). n jest potęgą b, wszystkie wyrazy są dodatnie, dodajemy do siebie f(n/stała), czyli w zasadzie niżej niż f(n) nie zejdziemy, bo dla dostatecznie dużych n ta stała traci znaczenie, więc w zasadzie

(16)

\begin{align} \sum_{j=0}^{log_{b}n - 1} a^{j}f\left(\frac{n}{b^{j}}\right) = \Theta(f(n)) \overset{\underset{\mathrm{(6)}}{}}{\Rightarrow} T(n) = \Theta(n^{\log_{b}a}) + \Theta(f(n)) \overset{\underset{\mathrm{zal}}{}}{\Rightarrow} T(n) = \Theta(f(n)) \end{align}

No bo z założenia mamy, że $f(n) = \Omega(n^{\log_{b}a})$.

Co kończy dowód przypadku 3, a zarazem tezy. Przypominam, że cały czas n było całkowitą potęgą b.

Dowód tak naprawdę

Jak już wspomniałem, przypadek musiałby być naprawdę patologiczny, jeżeliby tak się nie działo. Dlatego też dowód dla każdego n opiera się na dowodzeniu, że wzięcie podłogi czy sufitu z wyrażenia $\frac{n}{b^{j}}$ nie zmienia poprawności powyższego dowodu.
Ja go tu wkrótce umieszczę, na razie tyle.

Konkluzja

Jeżeli doszedłeś (doszłaś) do tego miejsca, przeczytawszy wszystko powyżej, gratuluję wolnego czasu ;). Jeżeliby się znalazł tam jakiś błąd - krzyczeć. No nic, jak widać, dowód ten nie jest trudny, trzeba umieć liczyć sumę ciągu… ;P