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

[newpuma (還很新)]

題目如圖

http://i.imgur.com/fCQA8oY.jpg

答案
http://i.imgur.com/5vXjwDy.jpg

我的理解是return的兩個副程式要合併應該會是4T(n/2)

但答案的意思好像是獨立成兩個子問題分別2T(n/2)+2T(n/2)所以O(n)+O(n)

但覺得這樣自我理解好像有點別出心裁，也不排除答案給錯，求解。

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.217.233
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1478622107.A.062.html
推 agamek900: 那個2*recursive(n/2)不是function call兩次的意思= =
→ agamek900: 所以是T(n/2)+T(n/2)
推 kyuudonut: 2T(n/2)就是兩個子問題阿 你寫成4T(n/2)會變成四個...
推 hut326521: 題目給的T(n)=2*T(n/2)+2*T(n/2)那兩個2是常數 是在
→ hut326521: 算數值 答案給的是算時間的所以只有兩個T(2/n)噢
原來如此，謝謝大家。
※ 編輯: newpuma (114.136.26.122), 11/09/2016 13:31:47