====== Złożoność algorytmów ======
**Termin zajęć:** 29/30.03.2011
**Do przygotowania:**
- Znajomość i rozumienie pojęć:
- Złożoność obliczeniowa.
- Złożoność pamięciowa:
- Działanie algorytmów "w miejscu".
- Złożoność pesymistyczna.
- Złożoność oczekiwana.
- 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:
- 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))
=== Zadania ===
- Metodą reukrencji uniwersalnej wyznacz złożoność obliczeniową algorytmu wyszukiwania binarnego.
- Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne: \\ T(n) = T(n-1) + \lfloor \log(n) \rfloor
- Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne: \\ T(n) = T(n/4) + T(3n/4) + n
- 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
* i(n)=n
* j(i)=n
* T(n)=n^2
for(i=0;i
* i(n)=n
* j(i)=n/2
* T(n)=n^2/2
for(i=0;i
* i(n)=n/2
* j(i)=i
* T(n)=n^2/8
for(i=0;i=1;j/=2)
OD
* i(n)=n/2
* j(i)=log i
* T(n)=n/2(log(n/2) - 1)