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 ${\displaystyle a>0,b>1,n_{0}>0}$ będą stałymi niezależnymi od ${\displaystyle n}$ i niech ${\displaystyle f(n)}$ będzie funkcją asymptotycznie nieujemną, czyli przyjmującą wartości nieujemne dla wystarczająco dużych ${\displaystyle n}$. Jeżeli funkcja ${\displaystyle T(n),}$ dla ${\displaystyle n>0}$ jest zdefiniowana następująco:

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

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

Tak zdefiniowane funkcje ${\displaystyle T}$ stanowią pewien schemat działania algorytmów typu „dziel i zwyciężaj” – problem o rozmiarze ${\displaystyle n}$ dzielony jest na ${\displaystyle a}$ podproblemów, każdy wielkości ${\displaystyle {\frac {n}{b}},}$ funkcja ${\displaystyle 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 ${\displaystyle n^{\log _{b}a}}$ czy ${\displaystyle f(n)}$ rośnie wielomianowo szybciej, i funkcja ta stanowi wówczas dokładne oszacowanie rekurencji ${\displaystyle T(n)}$. W przypadku 2 funkcje te rosną w takim samym tempie wielomianowym, jednak z możliwym czynnikiem polilogarytmicznym. ${\displaystyle 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 ${\displaystyle f(n)}$ i ${\displaystyle n^{\log _{b}a}}$ nie da się porównać asymptotycznie, np. gdy dla dowolnie dużych ${\displaystyle n}$, ${\displaystyle f(n)\gg n^{\log _{b}a}}$ i dla innych dowolnie dużych ${\displaystyle n}$, ${\displaystyle f(n)\ll n^{\log _{b}a}}$. W przypadkach 1 i 3 tempa wzrostu funkcji ${\displaystyle f(n)}$ i ${\displaystyle n^{\log _{b}a}}$ muszą różnić się o czynnik wielomianowy. Dodatkowo w przypadku 3 oprócz dominacji asymptotycznej wymagana jest pewna „regularność” funkcji ${\displaystyle 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

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

  ${\displaystyle a}$ nie jest stałą niezależną od ${\displaystyle n}$.

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

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

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

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

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

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

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

  Nie zachodzi warunek regularności:

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

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