作者ching4562 (monster710623)
看板Grad-ProbAsk
標題[理工] 資演 101交大 12題 遞迴和複雜度
時間Fri Dec 13 17:35:28 2019
https://i.imgur.com/8enKBhQ.jpg
問一下 像這種遞迴是有必要寫出來嗎
像我就寫不太出來紅色框起來的部分
然後就無從判斷起了
像這題也是 問一下怎解
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.200.215.242 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1576229730.A.FA6.html
1F：推 mistel: 題目不是說overhead是O(n)了嗎？ 就是每次迭代要額外負擔12/13 17:53
2F：→ mistel: 的成本，比方說merge sort每層要花O(n)去切割子問題，或 12/13 17:53
3F：→ mistel: 者binary search每層要花O(1)去檢查mid是否等於key 12/13 17:53
原來是這個意思 感謝
※ 編輯: ching4562 (123.193.248.215 臺灣), 12/13/2019 19:59:47
4F：→ mistel: 啊不好意思 merge sort是合併子問題花O(n)才對 打錯了 12/14 12:04