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

[filcogw (filcogw)]

題目：
T(n)  = 2T(n/2) + n/lg n
解法：利用展開帶入能求出
Ans : O(n*lglgn)

想問利用Master theory 判斷出 是case1
但為什麼不能使用（答案錯誤

----
Sent from BePTT

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.50.140.195 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1564748693.A.4D3.html
推 zuchang: Extended master theory
→ tayashot: http://imgur.com/gallery/iGFVZUA
推 Faker0613: 你定義沒看清楚 回去重看MT
→ AdonisLam: f(n)=O(n^(logba-ε)),前提是要找的到ε>0且為常數，這
→ AdonisLam: 個case1找出的ε會跟n有關
感謝前面的回達 但這題應該不適用 extended M T吧 只能展開帶入（？
※ 編輯: filcogw (1.200.211.95 臺灣), 08/06/2019 18:49:02
推 frank1688: 對，此題只能用展開代入，而不能用case1原因再你解出
→ frank1688: 來的不等式為log n >= n^ε（c取1情況下） ，此情況不
→ frank1688: 可能發生，因為ε要是大於0之常數