|
|
pl:dydaktyka:asd:cwiczenia:2011-compl [2011/04/04 11:48] ikaf met. graficzna |
pl:dydaktyka:asd:cwiczenia:2011-compl [2019/06/27 15:50] |
====== 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: \\ <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) = \Theta(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) = O(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> | |
| |
=== Zadania === | |
- Metodą reukrencji uniwersalnej wyznacz złożoność obliczeniową algorytmu wyszukiwania binarnego. | |
- Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne: \\ <latex>T(n) = T(n-1) + \lfloor \log(n) \rfloor</latex> | |
- Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne: \\ <latex>T(n) = T(n/4) + T(3n/4) + n</latex> | |
- Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne: \\ <latex>T(n) = T(\lfloor\sqrt{n}\rfloor) + \lfloor\sqrt{n}\rfloor</latex> | |
| |
=== Niejasności z zajęć === | |
Metoda graficzna: | |
<code> | |
for(i=0;i<n;i++) | |
for(j=0;j<n;j++) | |
OD | |
</code> | |
* i(n)=n | |
* j(i)=n | |
* T(n)=n^2 | |
| |
<code> | |
for(i=0;i<n;i++) | |
for(j=0;j<n;j+=2) | |
OD | |
</code> | |
* i(n)=n | |
* j(i)=n/2 | |
* T(n)=n^2/2 | |
| |
<code> | |
for(i=0;i<n;i+=2) | |
for(j=0;j<i;j++) | |
OD | |
</code> | |
* i(n)=n/2 | |
* j(i)=i | |
* T(n)=n^2/8 | |
| |
| |
<code> | |
for(i=0;i<n;i+=2) | |
for(j=i;j>=1;j/=2) | |
OD | |
</code> | |
* i(n)=n/2 | |
* j(i)=log i | |
* T(n)=n/2(log(n/2) - 1) | |
| |