Złożoność algorytmów

Termin zajęć: 29/30.03.2011

Do przygotowania:

  1. Znajomość i rozumienie pojęć:
    1. Złożoność obliczeniowa.
    2. Złożoność pamięciowa:
      1. Działanie algorytmów „w miejscu”.
    3. Złożoność pesymistyczna.
    4. Złożoność oczekiwana.
    5. Złożoność optymistyczna.

Zajęcia odbywać się będą głownie przy tablicy. Nie ma konieczności przynoszenia laptopów.


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))

Zadania

  1. Metodą reukrencji uniwersalnej wyznacz złożoność obliczeniową algorytmu wyszukiwania binarnego.
  2. Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne:
    T(n) = T(n-1) + \lfloor \log(n) \rfloor
  3. Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne:
    T(n) = T(n/4) + T(3n/4) + n
  4. Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne:
    T(n) = T(\lfloor\sqrt{n}\rfloor) + \lfloor\sqrt{n}\rfloor

Niejasności z zajęć

Metoda graficzna:

for(i=0;i<n;i++)
   for(j=0;j<n;j++)
      OD
  • i(n)=n
  • j(i)=n
  • T(n)=n^2
for(i=0;i<n;i++)
   for(j=0;j<n;j+=2)
      OD
  • i(n)=n
  • j(i)=n/2
  • T(n)=n^2/2
for(i=0;i<n;i+=2)
   for(j=0;j<i;j++)
      OD
  • i(n)=n/2
  • j(i)=i
  • T(n)=n^2/8
for(i=0;i<n;i+=2)
   for(j=i;j>=1;j/=2)
      OD
  • i(n)=n/2
  • j(i)=log i
  • T(n)=n/2(log(n/2) - 1)
pl/dydaktyka/asd/cwiczenia/2012-compl.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