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 13:49] ikaf |
pl:dydaktyka:asd:cwiczenia:2012-zlozonosc [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 69: | 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> | ||
