Różnice między wybraną wersją a wersją aktualną.
| — |
pl:dydaktyka:asd:cwiczenia:2012-compl [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| + | ====== 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) = 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> | ||
| + | |||
| + | === 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) | ||
