PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 資料結構 時間複雜度
作者:
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
http://imgur.com/gallery/iGFVZUA
作者:
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之常數
繼續閱讀
[理工] 離散題庫 2-115
ok8752665
[理工]
tayashot
[理工] 線代 冪零算子
AdonisLam
線代3-11
boof
[理工] 離散數學 計數問題
yoz4ni
[理工] 離散 4-1 生成函數 例題14
mimi9672
[理工] 離散 平面圖
AdonisLam
[理工] 離散 漢米爾頓環路
AdonisLam
現代P3-10
boof
[理工] 演算法divide and conquer
AdonisLam
Links
booklink
Contact Us: admin [ a t ] ucptt.com