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

看板Grad-ProbAsk作者 (filcogw)時間4年前 (2019/08/02 20:24), 4年前編輯推噓3(3推 0噓 5→)
留言8則, 5人參與, 4年前最新討論串2/3 (看更多)
題目： 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
推
08/02 20:34, 4年前 , 1F
Extended master theory
08/02 20:34, 1F
→
08/03 00:03, 4年前 , 2F
08/03 00:03, 2F
推
08/05 16:59, 4年前 , 3F
你定義沒看清楚 回去重看MT
08/05 16:59, 3F
→
08/06 11:29, 4年前 , 4F
f(n)=O(n^(logba-ε)),前提是要找的到ε>0且為常數，這
08/06 11:29, 4F
→
08/06 11:29, 4年前 , 5F
個case1找出的ε會跟n有關
08/06 11:29, 5F
感謝前面的回達 但這題應該不適用 extended M T吧 只能展開帶入（？ ※ 編輯: filcogw (1.200.211.95 臺灣), 08/06/2019 18:49:02
推
08/08 00:10, 4年前 , 6F
對，此題只能用展開代入，而不能用case1原因再你解出
08/08 00:10, 6F
→
08/08 00:10, 4年前 , 7F
來的不等式為log n >= n^ε（c取1情況下） ，此情況不
08/08 00:10, 7F
→
08/08 00:10, 4年前 , 8F
可能發生，因為ε要是大於0之常數
08/08 00:10, 8F
‣ 更多 filcogw 的文章
文章代碼(AID): #1TH2kLJJ (Grad-ProbAsk)
‣ 更多 filcogw 的文章
文章代碼(AID): #1TH2kLJJ (Grad-ProbAsk)