PTT
Submit
Submit
選擇語言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 演算法 P.31 32題
作者:
jojoboy0115
(jojo)
2018-12-06 22:59:55
https://i.imgur.com/dPEyEKP.jpg
請問為什麼它的recursion tree子節點,
不是分別為 (n/2) (n/2) ... (n/2) ←有八個 ?
其實也不可能是8個(n/2),這樣合起來就是4n...大於1
它的8c是怎麼判斷的?是把T(n/2)當成constant?
感謝大家~
作者:
skyHuan
(Huan)
2018-12-06 23:48:00
改後面的f(n)有可能是8個n/2他寫的那個是每步驟成本的意思在算T(n)這個步驟需要theta(1)=c的成本剩下call遞迴,就是8T(n/2)的部分就是成本樹的第二層,一樣每部theta(1)
作者:
jojoboy0115
(jojo)
2018-12-07 00:16:00
了解了,感謝sky大!
繼續閱讀
資結 時間複雜度
JocMon
[理工] 離散 函數問題
AAQ8
[理工] 計組上冊466(5)!
Aa841018
[理工] 計組上冊465!
Aa841018
[理工] 離散等價類
st945712
[理工] 資結題庫 指標變數
winson910343
[理工] 成大電通甲 線代or離散
hl654ck6
[理工] 台大線代
HY0869
[理工] OS 幾個問題 (process、特權指令)
skyHuan
[理工] 計組 下冊p.69
f255577
Links
booklink
Contact Us: admin [ a t ] ucptt.com