Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:asd:cwiczenia:2011-compl [2011/04/04 11:05] kkr |
pl:dydaktyka:asd:cwiczenia:2011-compl [2019/06/27 15:50] (aktualna) |
* iloraz <latex>n/b</latex> interpretujemy jako <latex>\lceil n/b \rceil</latex> lub jako <latex>\lfloor n/b \rfloor</latex> | * 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: | 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ż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) = O(n^{\log_{b}(a)})</latex> to, <latex>T(n) = \Theta(n^{\log_{b}(a)}\lg(n))</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> | - 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> |
| |
- 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(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> | - 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) |
| |