Twierdzenie o rekurencji uniwersalnej

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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

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

to:

  • Jeżeli \! f(n) = O(n^{log_ba-\epsilon}) dla pewnej stałej \! \epsilon > 0, to \! T(n) = \Theta (n^{log_ba})
  • Jeżeli \! f(n) = \Theta(n^{log_ba}), to \! T(n) = \Theta (n^{log_ba}\cdot \log\ n)
  • Jeżeli \! f(n) = \Omega(n^{log_ba+\epsilon}) dla pewnej stałej ε > 0 i jeżeli \! a\cdot f(\frac{n}{b})\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[edytuj | edytuj kod]

Każdy z trzech przypadków rekurencji uniwersalnej sprowadza się do stwierdzenia, która z funkcji \! n^{log_ba} 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[edytuj | edytuj kod]

Należy zdawać sobie sprawę, że twierdzenie o rekurencji uniwersalnej nie wyczerpuje wszystkich przypadków, nawet rekursji "typu" \! T(\frac{n}{b}) + f(n) - pomiędzy przypadkami twierdzenia istnieją "dziury". W pierwszym przypadku funkcja f musi być wielomianowo mniejsza od \! n^{log_ba}. 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[edytuj | edytuj kod]

Dla n będących potęgą b[edytuj | edytuj kod]

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

Lemat 1[edytuj | edytuj kod]

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

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

to

\! T(n)\ =\ \Theta (n^{log_ba})\ +\ \sum_{j = 0}^{\log_bn-1} a^j\cdot f(\frac{n}{b^j}) (*)
Dowód[edytuj | edytuj kod]

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(\frac{n}{b}). Dla każdego syna korzenia koszt każdego z jego a synów wynosi \! f(\frac{n}{b^2}). 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(\frac{n}{b^j}) oddalonych od korzenia o odległość j.
    • Koszt każdego liścia wynosi \! T(1)\ =\ \Theta (1), a ponieważ \! \frac{n}{b^{log_bn}}\ =\ 1 to każdy liść znajduje się na głębokości \! log_bn. Drzewo rekursji posiada \! a^{log_bn}\ =\ n^{log_ba} 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_bn-1} a^j\cdot f(\frac{n}{b^j}) a koszt liści to \! \Theta (n^{log_ba})

Lemat 2[edytuj | edytuj kod]

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_bn-1} a^j\cdot f(\frac{n}{b^j})

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

  • Jeżeli \! f(n) = O(n^{log_ba-\epsilon}) dla pewnej stałej \! \epsilon > 0, to \! g(n) = \Theta (n^{log_ba})
  • Jeżeli \! f(n) = \Theta(n^{log_ba}), to \! g(n) = \Theta (n^{log_ba}\cdot \lg\ n)
  • Jeżeli \! f(n) = \Omega(n^{log_ba+\epsilon}) dla pewnej stałej ε > 0 i jeżeli \! a\cdot f(\frac{n}{b})\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[edytuj | edytuj kod]

Dowód[edytuj | edytuj kod]

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

  • \! T(n)\ =\ \Theta (n^{log_ba})\ +\ O(n^{log_ba})\ =\ \Theta(n^{log_ba})
  • \! T(n) = \Theta (n^{log_ba}) + \Theta(n^{log_ba}\cdot \ln\ n) = \Theta(n^{log_ba}\cdot \ln\ n)
  • \! T(n) = \Theta (n^{log_ba}) + \Theta(f(n)) = \Theta(f(n)), ponieważ \! f(n) = \Omega (n^{log_ba + \epsilon})

Dla dowolnych n[edytuj | edytuj kod]

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\lfloor \frac{n}{b} \right\rfloor )\ +\ f(n) (1)

i

\! T(n) = a\cdot T(\left\lceil \frac{n}{b} \right\rceil )\ +\ f(n) (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]=\left\{ \begin{matrix} \ n &: i=0\\ 
\  \left\lceil \frac{n[i-1]}{b}  \right\rceil &:i>0 \end{matrix} \right.

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

\! T(n) = T(\left\lceil \frac{n}{b} \right\rceil)=\ T(\left\lceil \frac{\left\lceil \frac{n}{b}  \right\rceil }{b}  \right\rceil) = \cdots

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
  • \cdots
  • 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 _bn \right\rfloor

\! n[i] = n[\left\lfloor \log _bn \right\rfloor ] < \frac{n}{b^{\left\lfloor \log _bn \right\rfloor}} + \frac{b}{b-1} \leqslant \frac{n}{b^{\log _bn -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 _bn \right\rfloor ] i większych rozmiar problemu jest stały.