Re: [心得] Master theorem 不能套用的題目
在FRAXIS提供的文件中
https://goo.gl/t5ZSz6
p.2
"Theorem 1.
1.
if f(n) = O(n^(lg_b a) / lg n)(1+ε)
for some constant ε > 0,
then T(n) = Θ(n^(lg_b a)).
...
4.
if f(n) = Θ(n^(lg_b a) / lg n),
then T(n) = Θ(f(n) * lg n * lglg n)."
其中 f(n) = O(n^(lg_b a) / lg n)(1+ε)
上面這句是什麼意思?
若其意義等於 f(n) = O(n^(lg_b a) / lg n)
那1與4不就矛盾了?
因為若f(n)符合4的條件，則也會符合1的條件。
但是1與4算出的T(n)卻不同。
或者是1打錯了
應為 f(n) = O( n^(lg_b a) / (lg n)^(1+ε) ) ?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.248.67.183
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1507737861.A.492.html
※ 編輯: JKLee (111.248.67.183), 10/12/2017 00:21:20
推
10/12 05:47,
6年前
, 1F
10/12 05:47, 1F
討論串 (同標題文章)
完整討論串 (本文為第 3 之 3 篇)：