Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:asd:cwiczenia:2012-zlozonosc [2012/04/11 12:38] rmilo |
pl:dydaktyka:asd:cwiczenia:2012-zlozonosc [2012/04/16 20:20] ikaf |
||
|---|---|---|---|
| Linia 11: | Linia 11: | ||
| ===== Przykłady ===== | ===== Przykłady ===== | ||
| + | ==== Metoda podstawiania ==== | ||
| <latex>\begin{cases} | <latex>\begin{cases} | ||
| W(1) = 0 & \\ | W(1) = 0 & \\ | ||
| Linia 47: | Linia 48: | ||
| \end{cases}</latex> \\ co daje nam: \\ <latex>n + (n-1) + (n-2) + \dots + 1 = ((n+1)/2)*n = O(n^2)</latex> | \end{cases}</latex> \\ co daje nam: \\ <latex>n + (n-1) + (n-2) + \dots + 1 = ((n+1)/2)*n = O(n^2)</latex> | ||
| - | === Metoda rekurencji uniwersalnej === | + | ==== Metoda rekurencji uniwersalnej ==== |
| * Umożliwia szybkie wyznaczanie rozwiązania równania rekurencyjnego postaci: \\ <latex>T(n) = aT(n/b)+f(n)</latex> \\ gdzie: | * Umożliwia szybkie wyznaczanie rozwiązania równania rekurencyjnego postaci: \\ <latex>T(n) = aT(n/b)+f(n)</latex> \\ gdzie: | ||
| * a ≥ 1 | * a ≥ 1 | ||
| Linia 68: | Linia 69: | ||
| * a = 3, b = 4, f(n) = nlg(n), a zatem: | * a = 3, b = 4, f(n) = nlg(n), a zatem: | ||
| * <latex>n^{\log_{b}(a)} = n^{\log_{4}(3)} = O(n^{0,793})</latex> | * <latex>n^{\log_{b}(a)} = n^{\log_{4}(3)} = O(n^{0,793})</latex> | ||
| - | * Ponieważ <latex>f(n) = O(n^{\log_{4}(3)+\epsilon})</latex>, gdzie ε ≈ 0,2 więc stosuje się przypadek 3 jeżeli tylko możemy pokazać, że f(n) spełnia warunek regularności: | + | * Ponieważ <latex>f(n) = \Omega(n^{\log_{4}(3)+\epsilon})</latex>, gdzie ε ≈ 0,2 więc stosuje się przypadek 3 jeżeli tylko możemy pokazać, że f(n) spełnia warunek regularności: |
| * Dla dostatecznie dużych **n** mamy <latex>af(n/b) = 3(n/4)\lg(n/4) \leq (3/4)n\lg(n) = cf(n)</latex> dla **n=3/4**. | * Dla dostatecznie dużych **n** mamy <latex>af(n/b) = 3(n/4)\lg(n/4) \leq (3/4)n\lg(n) = cf(n)</latex> dla **n=3/4**. | ||
| * Korzystając zatem z przypadku 3. możemy zapisać że <latex>T(n) = \Theta(n\lg(n))</latex> | * Korzystając zatem z przypadku 3. możemy zapisać że <latex>T(n) = \Theta(n\lg(n))</latex> | ||
