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 uniwersalnej

Niech $a>0,b>1,n_0>0$ będą stałymi niezależnymi od $n$ i niech $f(n)$ będzie funkcją asymptotycznie nieujemną, czyli przyjmującą wartości nieujemne dla wystarczająco dużych $n$. Jeżeli funkcja $T(n),$ dla $n>0$ jest zdefiniowana następująco:

$T(n)=\{\begin{array}{cc}\mathrm{\Theta }(1)& \text{gdy }0<n<n_0\\ a\cdot T\left(\frac{n}{b}\right)+f(n)& \text{gdy }n⩾n_0\end{array},$

to:

1. jeżeli istnieje stała $ϵ>0,$ dla której $f(n)=O(n^{{\log }_{b}a-ϵ})$, to $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}),$
2. jeżeli istnieje stała $k$ dla której $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a}{\log }^{k}n),$ to

   $T(n)=\{\begin{array}{cc}\mathrm{\Theta }(n^{{\log }_{b}a})& \text{gdy }k<-1\\ \mathrm{\Theta }(n^{{\log }_{b}a}\cdot \log \log n)& \text{gdy }k=-1\\ \mathrm{\Theta }(n^{{\log }_{b}a}\cdot {\log }^{k+1}n)& \text{gdy }k>-1\end{array},$

3. jeżeli istnieje stała $ϵ>0,$ dla której $f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+ϵ})$ i jeżeli dodatkowo spełniony jest warunek regularności, $a\cdot f\left(\frac{n}{b}\right)⩽c\cdot f(n)$ dla pewnej stałej $c\in (0,1),$ dla dostatecznie dużych $n,$ to $T(n)=\mathrm{\Theta }(f(n)).$

Tak zdefiniowane funkcje $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.

Intuicyjna interpretacja

Przypadki 1 i 3 rekurencji uniwersalnej polegają na rozstrzyganiu, która z funkcji $n^{{\log }_{b}a}$ czy $f(n)$ rośnie wielomianowo szybciej, i funkcja ta stanowi wówczas dokładne oszacowanie rekurencji $T(n)$. W przypadku 2 funkcje te rosną w takim samym tempie wielomianowym, jednak z możliwym czynnikiem polilogarytmicznym. $T(n)$ ma wówczas rozwiązanie zbliżone do tego wspólnego tempa wzrostu.

„Dziury” rekurencji uniwersalnej

Twierdzenie o rekurencji uniwersalnej nie wyczerpuje wszystkich przypadków dla rekurencji w powyższej postaci. Nie znajduje ono zastosowania gdy funkcji $f(n)$ i $n^{{\log }_{b}a}$ nie da się porównać asymptotycznie, np. gdy dla dowolnie dużych $n$, $f(n)\gg n^{{\log }_{b}a}$ i dla innych dowolnie dużych $n$, $f(n)\ll n^{{\log }_{b}a}$. W przypadkach 1 i 3 tempa wzrostu funkcji $f(n)$ i $n^{{\log }_{b}a}$ muszą różnić się o czynnik wielomianowy. Dodatkowo w przypadku 3 oprócz dominacji asymptotycznej wymagana jest pewna „regularność” funkcji $f(n)$. Intuicyjnie, warunek regularności może nie być spełniony, jeśli funkcja ta rośnie zbyt wolno lokalnie, mimo wystarczającego globalnego tempa wzrostu.

Przykłady rekurencji nierozwiązywalnych metodą rekurencji uniwersalnej

• $T(n)=-0.5T\left(\frac{n}{2}\right)+n$
• $T(n)=T\left(\frac{3n}{2}\right)+n$
• $T(n)=2^{n}T\left(\frac{n}{2}\right)+n^n$

  $a$ nie jest stałą niezależną od $n$.

• $T(n)=2T\left(\frac{n}{2}\right)+\sin n$

  Funkcja $f(n)=\sin n$ nie jest asymptotycznie nieujemna.

• $T(n)=2T\left(\frac{n}{2}\right)+n^{1+\sin n}$

  Zarówno $f(n)=\mathrm{\Omega }(n^{1-1})=\mathrm{\Omega }(1)$ jak i $f(n)=O(n^{1+1})=O(n^2)$ - nie da się więc asymptotycznie porównać $f(n)$ i $n^{{\log }_{b}a}=n$.

• $T(n)=2T\left(\frac{n}{2}\right)+\frac{n}{{\log }_{2}n}$

  Nie jest zachowany wielomianowy wzrost między $f(n)$ i $n^{{\log }_{b}a}$.

• $T(n)=T\left(\frac{n}{2}\right)+{\log }_{2}n$

  Nie zachodzi warunek regularności:

  $a{\log }_2(n/b)={\log }_2(n/2)={\log }_{2}n-1=(1-1/{\log }_{2}n){\log }_{2}n$

  Czynnik $1-1/{\log }_{2}n$ jest mniejszy od 1 dla każdego $n>1$, ale wraz ze wzrostem $n$ zbliża się dowolnie do 1, dlatego nie istnieje stała $c<1$ taka że $(1-1/{\log }_{2}n){\log }_{2}n<c{\log }_{2}n$.