[理工] 資料結構 時間複雜度

作者: filcogw (filcogw)   2019-08-02 20:24:51
題目:
T(n) = 2T(n/2) + n/lg n
解法:利用展開帶入能求出
Ans : O(n*lglgn)
想問利用Master theory 判斷出 是case1
但為什麼不能使用(答案錯誤
作者: zuchang (chang)   2019-08-02 20:34:00
Extended master theory
作者: tayashot (Taya)   2019-08-03 00:03:00
作者: Faker0613 (月巴月巴)   2019-08-05 16:59:00
你定義沒看清楚 回去重看MT
作者: AdonisLam (Adonis)   2019-08-06 11:29:00
f(n)=O(n^(logba-ε)),前提是要找的到ε>0且為常數,這個case1找出的ε會跟n有關
作者: frank1688 (frank1688)   2019-08-08 00:10:00
對,此題只能用展開代入,而不能用case1原因再你解出來的不等式為log n >= n^ε(c取1情況下) ,此情況不可能發生,因為ε要是大於0之常數

Links booklink

Contact Us: admin [ a t ] ucptt.com