Twierdzenie o rekurencji uniwersalnej

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

Twierdzenie o rekurencji uniwersalnejEdytuj

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 interpretacjaEdytuj

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 uniwersalnejEdytuj

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 uniwersalnejEdytuj

Dla n będących potęgą bEdytuj

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

Lemat 1Edytuj

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ódEdytuj

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 2Edytuj

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ódEdytuj

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

  •  
  •  
  •   ponieważ  

Dla dowolnych nEdytuj

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.