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

看板Grad-ProbAsk作者 (還很新)時間9年前 (2016/11/09 00:21), 9年前編輯推噓3(3推 0噓 2→)
留言5則, 3人參與, 最新討論串1/1
題目如圖 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
推
11/09 00:40, , 1F
那個2*recursive(n/2)不是function call兩次的意思= =
11/09 00:40, 1F
→
11/09 00:41, , 2F
所以是T(n/2)+T(n/2)
11/09 00:41, 2F
推
11/09 00:42, , 3F
2T(n/2)就是兩個子問題阿 你寫成4T(n/2)會變成四個...
11/09 00:42, 3F
推
11/09 00:43, , 4F
題目給的T(n)=2*T(n/2)+2*T(n/2)那兩個2是常數 是在
11/09 00:43, 4F
→
11/09 00:43, , 5F
算數值 答案給的是算時間的所以只有兩個T(2/n)噢
11/09 00:43, 5F
原來如此，謝謝大家。 ※ 編輯: newpuma (114.136.26.122), 11/09/2016 13:31:47
‣ 更多 newpuma 的文章
文章代碼(AID): #1O8VkR1Y (Grad-ProbAsk)