Twierdzenie o rekurencji uniwersalnej


Twierdzenie o rekurencji uniwersalnej w encyklopedii

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.

Spis treści

Twierdzenie o rekurencji uniwersalnej | edytuj kod

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

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

to:

  • Jeżeli f ( n ) = O ( n log b a ϵ ) {\displaystyle f(n)=O(n^{\log _{b}a-\epsilon })} dla pewnej stałej ϵ > 0 , {\displaystyle \epsilon >0,} to T ( n ) = Θ ( n log b a ) {\displaystyle T(n)=\Theta (n^{\log _{b}a})}
  • Jeżeli f ( n ) = Θ ( n log b a ) , {\displaystyle f(n)=\Theta (n^{\log _{b}a}),} to T ( n ) = Θ ( n log b a log n ) {\displaystyle T(n)=\Theta (n^{\log _{b}a}\cdot \log n)}
  • Jeżeli f ( n ) = Ω ( n log b a + ϵ ) {\displaystyle f(n)=\Omega (n^{\log _{b}a+\epsilon })} dla pewnej stałej ε > 0 i jeżeli a f ( n b ) c f ( n ) {\displaystyle a\cdot f\left({\frac {n}{b}}\right)\leqslant c\cdot f(n)} dla pewnej stałej c ( 0 , 1 ) , {\displaystyle c\in (0,1),} dla dostatecznie dużych n, to T ( n ) = Θ ( f ( n ) ) {\displaystyle 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 {\displaystyle n} dzielony jest na a {\displaystyle a} podproblemów, każdy wielkości n b , {\displaystyle {\frac {n}{b}},} funkcja f {\displaystyle f} przedstawia koszt dzielenia problemu, oraz połączenia rozwiązań podproblemów.

Intuicyjna interpretacja | edytuj kod

Każdy z trzech przypadków rekurencji uniwersalnej sprowadza się do stwierdzenia, która z funkcji n log b a {\displaystyle n^{\log _{b}a}} 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 kod

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

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

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

Lemat 1 | 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:

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

to

T ( n ) = Θ ( n log b a ) + j = 0 log b n 1 a j f ( n b j ) {\displaystyle T(n)=\Theta (n^{\log _{b}a})+\sum _{j=0}^{\log _{b}n-1}a^{j}\cdot f\left({\frac {n}{b^{j}}}\right)} (*)
Dowód | 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 ( n b ) . {\displaystyle f\left({\frac {n}{b}}\right).} Dla każdego syna korzenia koszt każdego z jego a synów wynosi f ( n b 2 ) . {\displaystyle f\left({\frac {n}{b^{2}}}\right).} A więc istnieje dokładnie a 2 {\displaystyle a^{2}} węzłów leżących w odległości 2 od korzenia.
  • Ogólniej, dla j < b {\displaystyle j<b} istnieje a j {\displaystyle a^{j}} węzłów o koszcie f ( n b j ) {\displaystyle f\left({\frac {n}{b^{j}}}\right)} oddalonych od korzenia o odległość j.
    • Koszt każdego liścia wynosi T ( 1 ) = Θ ( 1 ) , {\displaystyle T(1)=\Theta (1),} a ponieważ n b log b n = 1 {\displaystyle {\frac {n}{b^{\log _{b}n}}}=1} to każdy liść znajduje się na głębokości log b n . {\displaystyle \log _{b}n.} Drzewo rekursji posiada a log b n = n log b a {\displaystyle a^{\log _{b}n}=n^{\log _{b}a}} 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 j = 0 log b n 1 a j f ( n b j ) {\displaystyle \sum _{j=0}^{\log _{b}n-1}a^{j}\cdot f\left({\frac {n}{b^{j}}}\right)} a koszt liści to Θ ( n log b a ) {\displaystyle \Theta (n^{\log _{b}a})}

Lemat 2 | 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 ) = j = 0 log b n 1 a j f ( n b j ) {\displaystyle g(n)=\sum _{j=0}^{\log _{b}n-1}a^{j}\cdot f\left({\frac {n}{b^{j}}}\right)}

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

    • Jeżeli f ( n ) = O ( n log b a ϵ ) {\displaystyle f(n)=O(n^{\log _{b}a-\epsilon })} dla pewnej stałej ϵ > 0 , {\displaystyle \epsilon >0,} to g ( n ) = Θ ( n log b a ) {\displaystyle g(n)=\Theta (n^{\log _{b}a})}
    • Jeżeli f ( n ) = Θ ( n log b a ) , {\displaystyle f(n)=\Theta (n^{\log _{b}a}),} to g ( n ) = Θ ( n log b a log n ) {\displaystyle g(n)=\Theta (n^{\log _{b}a}\cdot \log n)}
    • Jeżeli f ( n ) = Ω ( n log b a + ϵ ) {\displaystyle f(n)=\Omega (n^{\log _{b}a+\epsilon })} dla pewnej stałej ε > 0 i jeżeli a f ( n b ) c f ( n ) {\displaystyle a\cdot f\left({\frac {n}{b}}\right)\leqslant c\cdot f(n)} dla pewnej stałej c ( 0 , 1 ) , {\displaystyle c\in (0,1),} dla dostatecznie dużych n, to g ( n ) = Θ ( f ( n ) ) {\displaystyle g(n)=\Theta (f(n))}

Dowód | edytuj kod

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

  • T ( n ) = Θ ( n log b a ) + O ( n log b a ) = Θ ( n log b a ) {\displaystyle T(n)=\Theta (n^{\log _{b}a})+O(n^{\log _{b}a})=\Theta (n^{\log _{b}a})}
  • T ( n ) = Θ ( n log b a ) + Θ ( n log b a log n ) = Θ ( n log b a log n ) {\displaystyle T(n)=\Theta (n^{\log _{b}a})+\Theta (n^{\log _{b}a}\cdot \log n)=\Theta (n^{\log _{b}a}\cdot \log n)}
  • T ( n ) = Θ ( n log b a ) + Θ ( f ( n ) ) = Θ ( f ( n ) ) , {\displaystyle T(n)=\Theta (n^{\log _{b}a})+\Theta (f(n))=\Theta (f(n)),} ponieważ f ( n ) = Ω ( n log b a + ϵ ) {\displaystyle f(n)=\Omega (n^{\log _{b}a+\epsilon })}

Dla dowolnych n | edytuj kod

Dla dowolnych n (nie będących potęga b) wartość argumentu n b {\displaystyle {\frac {n}{b}}} może oznaczać n b {\displaystyle \left\lfloor {\frac {n}{b}}\right\rfloor } lub n b . {\displaystyle \left\lceil {\frac {n}{b}}\right\rceil .}

Odpowiednio górne i dolne oszacowanie dla funkcji

T ( n ) = a T ( n b ) + f ( n ) {\displaystyle T(n)=a\cdot T\left(\left\lfloor {\frac {n}{b}}\right\rfloor \right)+f(n)} (1)

i

T ( n ) = a T ( n b ) + f ( n ) {\displaystyle T(n)=a\cdot T\left(\left\lceil {\frac {n}{b}}\right\rceil \right)+f(n)} (2)

jest banalne do znalezienia, przy wykorzystaniu własności n b n b {\displaystyle \left\lfloor {\frac {n}{b}}\right\rfloor \geqslant {\frac {n}{b}}} i n b n b {\displaystyle \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 = { n : i = 0 n i 1 b : i > 0 {\displaystyle n[i]={\begin{cases}n&:i=0\\\left\lceil {\frac {n[i-1]}{b}}\right\rceil &:i>0\end{cases}}}

Wtedy schodzenie w dół rekursji oznacza jej rekurencyjne wywoływanie kolejno dla argumentów n 0 ,   n 1 ,   n 2 , {\displaystyle n[0],\ n[1],\ n[2],\dots }

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

Korzystając z nierówności a a + 1 {\displaystyle \left\lceil a\right\rceil \leqslant a+1} mamy:

  • n 0 n {\displaystyle n[0]\leqslant n}
  • n 1 n b + 1 {\displaystyle n[1]\leqslant {\frac {n}{b}}+1}
  • n 2 n b 2 + 1 b + 1 {\displaystyle n[2]\leqslant {\frac {n}{b^{2}}}+{\frac {1}{b}}+1}
  • n 3 n b 3 + 1 b 2 + 1 b + 1 {\displaystyle n[3]\leqslant {\frac {n}{b^{3}}}+{\frac {1}{b^{2}}}+{\frac {1}{b}}+1}
  • {\displaystyle \cdots }
  • n i n b i + k = 0 i 1 1 b k < n b i + k = 0 1 b k = n b i + b b 1 {\displaystyle 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 = log b n {\displaystyle i=\left\lfloor \log _{b}n\right\rfloor }

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

Na podstawie artykułu: "Twierdzenie o rekurencji uniwersalnej" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy