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{cases}\Theta (1)&{\text{gdy }}0<n<n_{0}\\a\cdot T\left({\frac {n}{b}}\right)+f(n)&{\text{gdy }}n\geqslant n_{0}\end{cases}},$

to:

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

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

3. jeżeli istnieje stała $\epsilon >0,$ dla której $f(n)=\Omega (n^{\log _{b}a+\epsilon })$ i jeżeli dodatkowo spełniony jest warunek regularności, $a\cdot f\left({\frac {n}{b}}\right)\leqslant c\cdot f(n)$ dla pewnej stałej $c\in (0,1),$ dla dostatecznie dużych $n,$ to $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$ 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)=\Omega (n^{1-1})=\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$.