mastertheorem.tex

\section{Twierdzenie o rekurencji uniwersalnej}

Popularną metodą rozwiązywania zadań jest metoda Dziel i Zwyciężaj.
Polega ona na podzieleniu problemu na mniejsze, rozwiązaniu ich w sposób rekurencyjny, a następnie na scaleniu wyniku w jeden.
Schemat tej metody jest przedstawiony jako Schemat \ref{recursion-example}.
\begin{algorithm}[h]
  \DontPrintSemicolon
  \SetAlgorithmName{Schemat}{}
    
  \If{$n \leq 1$}
  {
    rozwiąż trywialny przypadek
  }
  Stwórz $a$ podproblemów wielkości $n/b$ w czasie $D(n)$
  
  
  \For{$i \leftarrow 1$ to $a$}
  {
   	wykonaj procedurę \texttt{Dziel\_i\_zwyciezaj} rekurencyjnie dla $i$-tego podproblemu
  }
  Połącz wyniki w czasie $P(n)$
  \caption{Procedura \texttt{Dziel\_i\_zwyciezaj}}
  \label{recursion-example}
\end{algorithm}

Złożoność takiego algorytmu możemy zapisać zależnością rekurencyjną $T(n) = aT(n/b) + \Theta(n^k \log^{p} n)$ przy czym $P(n) + D(n) \in \Theta(n^k \log^{p} n)$.
Jednakże zależność rekurencyjna na czas działania algorytmu nie zawsze nas satysfakcjonuje.
Zazwyczaj chcielibyćmy uzyskać wzór zwarty.
Do tego celu służy poniższe twierdzenie, znane Twierdzeniem o rekurencji uniwersalnej.

\begin{theorem}
 Niech $T(n) = aT(n/b) + \Theta(n^k \log^{p} n)$ oraz $a \geq 1$, $b > 1$, $k \geq 0$ oraz $p$ liczby rzeczywiste.
 Wtedy
\begin{enumerate}
\item jeżeli $a > b^k$, to $T(n) \in \Theta(n^{\log_b a})$ \label{mt-1}
\item jeżeli $a = b^k$ oraz 
\begin{enumerate}
 \item $p > -1$ to $T(n) \in \Theta(n^{\log_b a} \log^{p + 1} n)$ \label{mt-2a}
 \item $p = -1$ to $T(n) \in \Theta(n^{\log_b a} \log \log n)$ \label{mt-2b}
 \item $p < -1$ to $T(n) \in \Theta(n^{\log_b a})$ \label{mt-2c}
\end{enumerate}
\item jeżeli $a < b^k$ oraz
\begin{enumerate}
 \item $p \geq 0$ to $T(n) \in \Theta(n^k \log^{p} n)$ \label{mt-3a}
 \item $p < 0$ to $T(n) \in O(n^k)$ \label{mt-3b}
\end{enumerate}
\end{enumerate}
 \label{Master}
\end{theorem}

\begin{proof}
 TODO TODO TODO.
\end{proof}

\subsection{Przykłady wykorzystania twierdzenia}

W rozdziale \ref{sec:merge-sort} zapoznamy się z algorytmem sortowania przez scalanie.
\comment{Nie podoba mi się to, że to jest osobny podrozdział.
Nie wiem czy to powinnien być osobny akapit, tabelka czy może coś jeszcze innego.}
Jego złożoność określona jest wzorem rekurencyjnym $T(n) = 2 \cdot T(n/2) + \Theta(n)$.
W tym przypadku $a = 2$, $b = 2$, $k = 1$ oraz $p = 0$.
Ponieważ $a = b^k$ sprawdzamy dodatkowo, że $p > -1$ i otrzymujemy, że w naszym przypadku powinniśmy skorzystać z pkt \ref{mt-2a}.
Otrzymujemy, że złożoność naszego algorytmu jest $\Theta(n^{\log_b a} \log^{p + 1} n)$ czyli $\Theta(n\log n)$.

W rodziale \ref{sec:bitoniczne} opisany został algorytm sortowania bitonicznego.
Jego złożoność określona jest wzorem $T(n) = 2 \cdot T(n/2) + \Theta(n \log n)$.
W tym przypadeku $a = 2$, $b = 2$, $k=1$ i $p = 1$.
Ponieważ $a = b^k$ i $p > -1$ korzystamy z punktu \ref{mt-2a}.
Otrzymujemy złożoność $\Theta(n \log^2 n)$.

\comment{Naprawić referencję.}
W rozdziale \ref{sec:karatsuba} opisany jest algorytm Karatsuby. Jego złożoność opisana jest rekurencyjnym wzorem $3 T(n/2) + \Theta(n)$.
W tym przypadku $a = 3$, $b = 2$, $k=1$ i $p=0$.
Ponieważ $a > b^k$ korzystamy z punktu \ref{mt-1}.
Otrzymujemy złożoność $\Theta(n^{\log_{2} 3})$ czyli około $\Theta(n^{1.585}).$

Wyszukiwanie binarne to algorytm klasy Dziel i Zwyciężaj wyszukujący element w posortowanym ciągu.
Ma złożoność opisaną rekurencyjnym wzorem $T(n) = T(n/2) + \Theta(1)$.
Mamy więc $a = 1$, $b = 2$, $k = p = 0$.
Ponieważ $a = b^k$ i $p > -1$ korzystamy z punktu \ref{mt-2a}.
Otrzymujemy złożoność $\Theta(\log n)$.

Algorytm Strassena jest opisany w rodziale \ref{sec:strassen}.
Jego złożoność opisana jest rekurencyjnym wzorem $T(n) = 7 \cdot T(n/2) + \Theta(n^2)$.
W tym przypadku mamy $a = 7$, $b = 2$, $k = 2$, $p = 0$.
Jako, że $a > b^k$ wykorzystamy punkt \ref{mt-1}.
Otrzymujemy złożoność $\Theta(n^{\log_{2} 7})$ czyli około $\Theta(n^{2.807})$