Twierdzenie o rekurencji uniwersalnej

Z Wikipedii

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

Spis treści

1 Twierdzenie o rekurencji uniwersalnej
2 Intuicyjna interpretacja
3 "Dziury" rekurencji uniwersalnej
4 Dowód twierdzenia o rekurencji uniwersalnej
- 4.1 Dla n będących potęgą b
- 4.2 Dla dowolnych n

[edytuj] Twierdzenie o rekurencji uniwersalnej

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

$T(n)=\left\{ \begin{matrix} \ \Theta (1) &: 1\le n < b\\ \ a\cdot T(\frac{n}{b}) + f(n)&:n\ge 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 \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})\le 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 funcje 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.

[edytuj] Intuicyjna interpretacja

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".

[edytuj] "Dziury" rekurencji uniwersalnej

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 mniejszoś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.

[edytuj] Dowód twierdzenia o rekurencji uniwersalnej

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

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

[edytuj] Lemat 1

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})$ (*)

[edytuj] 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(\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. nie bę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})$

[edytuj] 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_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 \ln\ n)$
Jeżeli $\! f(n) = \Omega(n^{log_ba+\epsilon})$ dla pewnej stałej ε > 0 i jeżeli $\! a\cdot f(\frac{n}{b})\le c\cdot f(n)$ dla pewnej stałej $\! c \in (0,1)$ , dla dostatecznie dużych n, to $\! g(n)=\Theta(f(n))$

[edytuj] Dowód

Korzystając z oszacowania z lematu 2 dla sumy (*). Dla kolenych 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})$

[edytuj] 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\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 \ge \frac{n}{b}$ i $\! \left\lceil \frac{n}{b} \right\rceil \le \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 \le a\ +\ 1$ mamy:

$n[0] \le n$
$n[1] \le \frac{n}{b}\ +\ 1$
$n[2] \le \frac{n}{b^2}\ +\ \frac{1}{b}\ +\ 1$
$n[3] \le \frac{n}{b^3}\ +\ \frac{1}{b^2}\ +\ \frac{1}{b}\ +\ 1$
$\cdots$
$n[i] \le \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}\ \le \ \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.

Tomasz Piszcz wygrał żużlowy turniej w Lublinie

Tomasz Piszcz wygrał w Lublinie żużlowy turniej zaliczany do Pucharu MACEC (Stowarzyszenia Motocyklowego Krajów Europy Środkowej).

MŚ w piłce nożne plażowej: zacięte półfinały

Brazylia zagra z Włochami w finale rozgrywanych w Marsylii mistrzostw świata w piłce nożnej plażowej.

MŚJ klasy 470: słaby wiatr przyniósł zmiany liderów

Pierwszy dzień wyścigów finałowych mistrzostw świata juniorów w żeglarskiej klasie 470 przyniósł spore zmiany w klasyfikacji generalnej. Zarówno wśród kobiet jak i mężczyzn nastąpiły zmiany liderów.

Niemcy mistrzami Europy U-19

Piłkarska reprezentacja Niemiec pokonała Włochów 3:1 (1:0) w meczu finałowym mistrzostw Europy do lat 19 w czeskim Jabloncu.

Puchar Intertoto: zadecydował 24. karny!

Piłkarze Aston Villa Birmingham pokonali na własnym boisku Odense BK 1:0 (0:0) w rewanżowym spotkaniu trzeciej rundy Pucharu Intertoto. W nagrodę "The Villans" wystąpią w drugiej rundzie kwalifikacyjnej Pucharu UEFA.

Linki: Strona g��wna

Encyklopedia

Twierdzenie o rekurencji uniwersalnej

Z Wikipedii

Spis treści

[edytuj] Twierdzenie o rekurencji uniwersalnej

[edytuj] Intuicyjna interpretacja

[edytuj] "Dziury" rekurencji uniwersalnej

[edytuj] Dowód twierdzenia o rekurencji uniwersalnej

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

[edytuj] Lemat 1

[edytuj] Dowód

[edytuj] Lemat 2

[edytuj] Dowód

[edytuj] Dowód

[edytuj] Dla dowolnych n