Twierdzenie o rekurencji uniwersalnej

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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

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

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

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

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

Lemat 1[edytuj | edytuj kod]

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:

to

(*)
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 – 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 | 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:

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

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

  • ponieważ

Dla dowolnych n[edytuj | edytuj kod]

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.