Obliczanie złożoności algorytmów

Do przygotowania

  1. 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))
pl/dydaktyka/asd/cwiczenia/2012-zlozonosc.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0