作者filcogw (filcogw)
看板Grad-ProbAsk
標題[理工] 資料結構 時間複雜度
時間Fri Aug 2 20:24:51 2019
題目：
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1564748693.A.4D3.html
1F：推 zuchang: Extended master theory08/02 20:34
3F：推 Faker0613: 你定義沒看清楚 回去重看MT08/05 16:59
4F：→ AdonisLam: f(n)=O(n^(logba-ε)),前提是要找的到ε>0且為常數，這08/06 11:29
5F：→ AdonisLam: 個case1找出的ε會跟n有關08/06 11:29
感謝前面的回達 但這題應該不適用 extended M T吧 只能展開帶入（？
※ 編輯: filcogw (1.200.211.95 臺灣), 08/06/2019 18:49:02
6F：推 frank1688: 對，此題只能用展開代入，而不能用case1原因再你解出 08/08 00:10
7F：→ frank1688: 來的不等式為log n >= n^ε（c取1情況下） ，此情況不 08/08 00:10
8F：→ frank1688: 可能發生，因為ε要是大於0之常數 08/08 00:10