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]

Jeżeli funkcja , dla i funkcji dodatniej , jest zdefiniowana następująco:

to:

  • Jeżeli dla pewnej stałej , to
  • Jeżeli , to
  • Jeżeli dla pewnej stałej ε > 0 i jeżeli dla pewnej stałej , dla dostatecznie dużych n, to

Tak zdefiniowane funkcje T stanowią pewien schemat działania algorytmów typu "dziel i zwyciężaj" - problem o rozmiarze dzielony jest na podproblemów, każdy wielkości , funkcja przedstawia koszt dzielenia problemu, oraz połączenia rozwiązań podproblemów.

Intuicyjna interpretacja[edytuj]

Każdy z trzech przypadków rekurencji uniwersalnej sprowadza się do stwierdzenia, która z funkcji 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]

Należy zdawać sobie sprawę, że twierdzenie o rekurencji uniwersalnej nie wyczerpuje wszystkich przypadków, nawet rekursji "typu" - pomiędzy przypadkami twierdzenia istnieją "dziury". W pierwszym przypadku funkcja f musi być wielomianowo mniejsza od . 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]

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

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

Lemat 1[edytuj]

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:

to

(*)
Dowód[edytuj]

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

  • Koszt korzenia drzewa wynosi f(n), a jego każdego z a synów - . Dla każdego syna korzenia koszt każdego z jego a synów wynosi . A więc istnieje dokładnie węzłów leżących w odległości 2 od korzenia.
  • Ogólniej, dla istnieje węzłów o koszcie oddalonych od korzenia o odległość j.
    • Koszt każdego liścia wynosi , a ponieważ to każdy liść znajduje się na głębokości . Drzewo rekursji posiada 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 a koszt liści to

Lemat 2[edytuj]

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:

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

    • Jeżeli dla pewnej stałej , to
    • Jeżeli , to
    • Jeżeli dla pewnej stałej ε > 0 i jeżeli dla pewnej stałej , dla dostatecznie dużych n, to
Dowód[edytuj]

Dowód[edytuj]

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

  • , ponieważ

Dla dowolnych n[edytuj]

Dla dowolnych n (nie będących potęga b) wartość argumentu może oznaczać lub .

Odpowiednio górne i dolne oszacowanie dla funkcji

(1)

i

(2)

jest banalne do znalezienia, przy wykorzystaniu własności i

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

Niech

Wtedy schodzenie w dół rekursji oznacza jej rekurencyjne wywoływanie kolejno dla argumentów

Korzystając z nierówności mamy:

Dla

Oznacza to, że dla wywołań rekursji na poziomie co najmniej i większych rozmiar problemu jest stały.