Różnice między wybraną wersją a wersją aktualną.
|
pl:dydaktyka:asd:cwiczenia:2012-zlozonosc [2012/04/16 20:20] ikaf |
pl:dydaktyka:asd:cwiczenia:2012-zlozonosc [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== 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 ==== | ||
| - | <latex>\begin{cases} | ||
| - | W(1) = 0 & \\ | ||
| - | W(n) = W(\lfloor n/2 \rfloor) + W(\lceil n/2\rceil) + n & \text{dla } n > 1} | ||
| - | \end{cases}</latex> | ||
| - | |||
| - | Jak sobie radzimy z rekurencją? Podstawiamy <latex>n=2^k</latex>. | ||
| - | Wtedy mamy: \\ | ||
| - | <latex>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)</latex>\\ | ||
| - | <latex>W(n) = A(n) = n\log(n) </latex> | ||
| - | * Kolejny przykład metody podstawiania: \\ <latex>\begin{cases} | ||
| - | W(1) = 0 & \\ | ||
| - | W(n) = W(\lfloor n/2 \rfloor) + W(\lceil n/2\rceil) + 1 & \text{dla } n > 1} | ||
| - | \end{cases}</latex> \\ oraz \\ <latex>\begin{cases} | ||
| - | W(1) = 1 & \\ | ||
| - | W(n) = W(\lfloor n/2 \rfloor) + W(\lceil n/2\rceil) + 1 & \text{dla } n > 1} | ||
| - | \end{cases}</latex> \\ W obu powyższych przykładach robimy to samo podstawienie i możemy zaobserwować że złożoność jest liniowa. Wyprowadzenie: \\ <latex> | ||
| - | 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 = | ||
| - | </latex> \\ Teraz dla przypadku kiedy <latex>W(1) = 0</latex>: \\ <latex>= 0 + 2^k-1 = n-1</latex> \\ oraz dla przypadku kiedy <latex>W(1) = 1</latex>: \\ <latex>= 2^k + 2^{k-1} + 2^{k-2} + \dots + 2 + 1 = \\ = 2^{k+1} -1 = \\ = 2*2^k-1 = \\ = 2n-1</latex> | ||
| - | |||
| - | * Jeszcze jeden przykład: \\ <latex>\begin{cases} | ||
| - | W(1) = 0 & \\ | ||
| - | W(n) = 2W(\lfloor \sqrt{n} \rfloor) + \log{n} & \text{dla } n > 1} | ||
| - | \end{cases}</latex> \\ Rozwiązanie powyższego przykładu jest następujące: | ||
| - | * Wstawiamy <latex>n = 2^m</latex>, czyli <latex>m = \log(n)</latex> \\ <latex>W(2^m) = 2W(\lfloor 2^{m/2} \rfloor) + m | ||
| - | </latex> \\ następnie wykonujemy kolejne podstawienie: \\ <latex> S(m) = W(2^m) </latex> \\ i w ten sposób otrzymujemy: \\ <latex> S(m) = 2S(m/2) + m</latex> \\ co jest równe: \\ <latex>m\log(m)</latex> \\ | ||
| - | Powracając i wstawiając do wcześniejszego wzoru otrzymujemy: \\ <latex> W(2^m) = 2m\log m + m </latex> \\ i ostatecznie wstawiając \\ <latex>m = \log(n)</latex> \\ dostajemy: \\ <latex>W(n) = 2\log(n)\log(\log(n)) + \log(n)</latex> \\ co daje złożoność: \\ <latex>O(n) = \log(n)\log(\log(n))</latex> | ||
| - | * 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: \\ <latex>\begin{cases} | ||
| - | W(1) = 0 & \\ | ||
| - | W(n) = W(\lfloor n/2 \rfloor) + W(\lceil n/2 \rceil) + n & } | ||
| - | \end{cases}</latex> \\ co daje nam złożoność logarytmiczną. | ||
| - | * Złożoność pesymistyczna jest wyrażona następującym równaniem rekurencyjnym: \\ <latex>\begin{cases} | ||
| - | W(1) = 0 & \\ | ||
| - | W(n) = W(n-1) + n & } | ||
| - | \end{cases}</latex> \\ co daje nam: \\ <latex>n + (n-1) + (n-2) + \dots + 1 = ((n+1)/2)*n = O(n^2)</latex> | ||
| - | |||
| - | ==== Metoda rekurencji uniwersalnej ==== | ||
| - | * Umożliwia szybkie wyznaczanie rozwiązania równania rekurencyjnego postaci: \\ <latex>T(n) = aT(n/b)+f(n)</latex> \\ gdzie: | ||
| - | * a ≥ 1 | ||
| - | * b > 1 | ||
| - | * f(n) jest funkcją asymptotycznie dodatnią. | ||
| - | * iloraz <latex>n/b</latex> interpretujemy jako <latex>\lceil n/b \rceil</latex> lub jako <latex>\lfloor n/b \rfloor</latex> | ||
| - | * Wtedy **T(n)** może być ograniczona asymptotycznie w następujący sposób: | ||
| - | - Jeżeli <latex>f(n) = O(n^{\log_{b}(a)-\epsilon})</latex> dla pewnej stałej ε > 0 to, <latex>T(n) = \Theta(n^{\log_{b}(a)})</latex> | ||
| - | - Jeśli <latex>f(n) = \Theta(n^{\log_{b}(a)})</latex> to, <latex>T(n) = \Theta(n^{\log_{b}(a)}\lg(n))</latex> | ||
| - | - Jeżeli <latex>f(n) = \Omega(n^{\log_{b}(a)+\epsilon})</latex> dla pewnej stałej ε > 0 oraz <latex> af(n/b) \leq cf(n)</latex> dla pewnej stałej **c** i wszystkich dostatecznie dużych **n**, to <latex>T(n) = \Theta(f(n))</latex> | ||
| - | * **Teraz może prosty przykład:** \\ Mamy równanie: \\ <latex>T(n) = 9T(n/3)+n</latex> \\ Rozwiązanie: | ||
| - | * a = 9, b = 3, f(n) = n, a zatem: | ||
| - | * <latex>n^{\log_{b}(a)} = n^{\log_{3}(9)} = \Theta(n^2)</latex> | ||
| - | * ponieważ <latex>f(n) = O(n^{\log_{3}(9)-\epsilon})</latex>, gdzie ε = 1 to możemy zastosować przypadek 1 z twierdzenia i wywnioskować że \\ <latex>T(n) = \Theta(n^2)</latex> | ||
| - | * **Drugi przykład:** \\ Mamy równanie: \\ <latex>T(n) = T(2n/3)+1</latex> \\ Rozwiązanie: | ||
| - | * a = 1, b = 3/2, f(n) = 1, a zatem: | ||
| - | * <latex>n^{\log_{b}(a)} = n^{\log_{3/2}(1)} = n^0 = \Theta(1)</latex> | ||
| - | * Stosujemy tutaj przypadek 2 gdyż <latex>f(n) = \Theta(n^{\log_{3/2}(1)}) = \Theta(1)</latex>, i z twierdzenia możemy wywnioskować że \\ <latex>T(n) = \Theta(\lg(n))</latex> | ||
| - | * **Trzeci przykład:** \\ Mamy równanie: \\ <latex>T(n) = 3T(n/4)+n\lg(n)</latex> \\ Rozwiązanie: | ||
| - | * a = 3, b = 4, f(n) = nlg(n), a zatem: | ||
| - | * <latex>n^{\log_{b}(a)} = n^{\log_{4}(3)} = O(n^{0,793})</latex> | ||
| - | * Ponieważ <latex>f(n) = \Omega(n^{\log_{4}(3)+\epsilon})</latex>, 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 <latex>af(n/b) = 3(n/4)\lg(n/4) \leq (3/4)n\lg(n) = cf(n)</latex> dla **n=3/4**. | ||
| - | * Korzystając zatem z przypadku 3. możemy zapisać że <latex>T(n) = \Theta(n\lg(n))</latex> | ||
