[理工] 資料結構時間複雜度 filcogw PTT批踢踢實業坊

作者: 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之常數

繼續閱讀