Obliczanie złożoności algorytmów

Do przygotowania

Znajomość i rozumienie pojęć:
1. Złożoność obliczeniowa.
2. Złożoność pamięciowa.
3. Złożoność pesymistyczna.
4. Złożoność oczekiwana.
5. 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:
  1. Jeżeli $f(n) = O(n^{\log_{b}(a)-\epsilon})$ dla pewnej stałej ε > 0 to, $T(n) = \Theta(n^{\log_{b}(a)})$
  2. Jeśli $f(n) = \Theta(n^{\log_{b}(a)})$ to, $T(n) = \Theta(n^{\log_{b}(a)}\lg(n))$
  3. 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))$