====== Obliczanie złożoności algorytmów ======
===== Do przygotowania =====
- Znajomość i rozumienie pojęć:
- Złożoność obliczeniowa.
- Złożoność pamięciowa.
- Złożoność pesymistyczna.
- Złożoność oczekiwana.
- Złożoność optymistyczna.
===== Przykłady =====
==== Metoda podstawiania ====
\begin{cases}
W(1) = 0 & \\
W(n) = W(\lfloor n/2 \rfloor) + W(\lceil n/2\rceil) + n & \text{dla } n > 1}
\end{cases}
Jak sobie radzimy z rekurencją? Podstawiamy n=2^k.
Wtedy mamy: \\
W(2^k) = 2 W(2^{k-1}) + 2^k = \\ = 2(2W(2^{k-2}) + 2^{k-1}) + 2^k = \\ = 2^2W(2^{k-2})+ 2^k + 2^k = \\ = 2^kW(2^0) + k2^k = \\ = 0 + n\log(n)\\
W(n) = A(n) = n\log(n)
* Kolejny przykład metody podstawiania: \\ \begin{cases}
W(1) = 0 & \\
W(n) = W(\lfloor n/2 \rfloor) + W(\lceil n/2\rceil) + 1 & \text{dla } n > 1}
\end{cases} \\ oraz \\ \begin{cases}
W(1) = 1 & \\
W(n) = W(\lfloor n/2 \rfloor) + W(\lceil n/2\rceil) + 1 & \text{dla } n > 1}
\end{cases} \\ W obu powyższych przykładach robimy to samo podstawienie i możemy zaobserwować że złożoność jest liniowa. Wyprowadzenie: \\
W(2^k) = 2 W(2^{k-1}) + 1 = \\ = 2(2W(2^{k-2}) + 1) + 1 = \\ = 2(2(2W(2^{k-3}) + 1) + 1) + 1 = \\ = 2^3W(2^{k-3})+ 4 + 2 + 1 = \\ = 2^kW(2^0) + 2^{k-1} + 2^{k-2} + \dots + 2 + 1 =
\\ Teraz dla przypadku kiedy W(1) = 0: \\ = 0 + 2^k-1 = n-1 \\ oraz dla przypadku kiedy W(1) = 1: \\ = 2^k + 2^{k-1} + 2^{k-2} + \dots + 2 + 1 = \\ = 2^{k+1} -1 = \\ = 2*2^k-1 = \\ = 2n-1
* Jeszcze jeden przykład: \\ \begin{cases}
W(1) = 0 & \\
W(n) = 2W(\lfloor \sqrt{n} \rfloor) + \log{n} & \text{dla } n > 1}
\end{cases} \\ Rozwiązanie powyższego przykładu jest następujące:
* Wstawiamy n = 2^m, czyli m = \log(n) \\ W(2^m) = 2W(\lfloor 2^{m/2} \rfloor) + m
\\ następnie wykonujemy kolejne podstawienie: \\ S(m) = W(2^m) \\ i w ten sposób otrzymujemy: \\ S(m) = 2S(m/2) + m \\ co jest równe: \\ m\log(m) \\
Powracając i wstawiając do wcześniejszego wzoru otrzymujemy: \\ W(2^m) = 2m\log m + m \\ i ostatecznie wstawiając \\ m = \log(n) \\ dostajemy: \\ W(n) = 2\log(n)\log(\log(n)) + \log(n) \\ co daje złożoność: \\ O(n) = \log(n)\log(\log(n))
* W tym miejscu warto zwrócić uwagę obliczenia złożoności oczekiwanej i pesymistycznej algorytmu QuickSort:
* Złożoność oczekiwana A(n) to rozwiązanie takiego równania rekurencyjnego: \\ \begin{cases}
W(1) = 0 & \\
W(n) = W(\lfloor n/2 \rfloor) + W(\lceil n/2 \rceil) + n & }
\end{cases} \\ co daje nam złożoność logarytmiczną.
* Złożoność pesymistyczna jest wyrażona następującym równaniem rekurencyjnym: \\ \begin{cases}
W(1) = 0 & \\
W(n) = W(n-1) + n & }
\end{cases} \\ co daje nam: \\ n + (n-1) + (n-2) + \dots + 1 = ((n+1)/2)*n = O(n^2)
==== Metoda rekurencji uniwersalnej ====
* Umożliwia szybkie wyznaczanie rozwiązania równania rekurencyjnego postaci: \\ T(n) = aT(n/b)+f(n) \\ gdzie:
* a ≥ 1
* b > 1
* f(n) jest funkcją asymptotycznie dodatnią.
* iloraz n/b interpretujemy jako \lceil n/b \rceil lub jako \lfloor n/b \rfloor
* Wtedy **T(n)** może być ograniczona asymptotycznie w następujący sposób:
- Jeżeli f(n) = O(n^{\log_{b}(a)-\epsilon}) dla pewnej stałej ε > 0 to, T(n) = \Theta(n^{\log_{b}(a)})
- Jeśli f(n) = \Theta(n^{\log_{b}(a)}) to, T(n) = \Theta(n^{\log_{b}(a)}\lg(n))
- Jeżeli f(n) = \Omega(n^{\log_{b}(a)+\epsilon}) dla pewnej stałej ε > 0 oraz af(n/b) \leq cf(n) dla pewnej stałej **c** i wszystkich dostatecznie dużych **n**, to T(n) = \Theta(f(n))
* **Teraz może prosty przykład:** \\ Mamy równanie: \\ T(n) = 9T(n/3)+n \\ Rozwiązanie:
* a = 9, b = 3, f(n) = n, a zatem:
* n^{\log_{b}(a)} = n^{\log_{3}(9)} = \Theta(n^2)
* ponieważ f(n) = O(n^{\log_{3}(9)-\epsilon}), gdzie ε = 1 to możemy zastosować przypadek 1 z twierdzenia i wywnioskować że \\ T(n) = \Theta(n^2)
* **Drugi przykład:** \\ Mamy równanie: \\ T(n) = T(2n/3)+1 \\ Rozwiązanie:
* a = 1, b = 3/2, f(n) = 1, a zatem:
* n^{\log_{b}(a)} = n^{\log_{3/2}(1)} = n^0 = \Theta(1)
* Stosujemy tutaj przypadek 2 gdyż f(n) = \Theta(n^{\log_{3/2}(1)}) = \Theta(1), i z twierdzenia możemy wywnioskować że \\ T(n) = \Theta(\lg(n))
* **Trzeci przykład:** \\ Mamy równanie: \\ T(n) = 3T(n/4)+n\lg(n) \\ Rozwiązanie:
* a = 3, b = 4, f(n) = nlg(n), a zatem:
* n^{\log_{b}(a)} = n^{\log_{4}(3)} = O(n^{0,793})
* Ponieważ f(n) = \Omega(n^{\log_{4}(3)+\epsilon}), gdzie ε ≈ 0,2 więc stosuje się przypadek 3 jeżeli tylko możemy pokazać, że f(n) spełnia warunek regularności:
* Dla dostatecznie dużych **n** mamy af(n/b) = 3(n/4)\lg(n/4) \leq (3/4)n\lg(n) = cf(n) dla **n=3/4**.
* Korzystając zatem z przypadku 3. możemy zapisać że T(n) = \Theta(n\lg(n))