[理工] 資演 101交大 12題 遞迴和複雜度

[ching4562 (monster710623)]

https://i.imgur.com/8enKBhQ.jpg
問一下 像這種遞迴是有必要寫出來嗎
像我就寫不太出來紅色框起來的部分
然後就無從判斷起了
像這題也是 問一下怎解

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.200.215.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1576229730.A.FA6.html
推 mistel: 題目不是說overhead是O(n)了嗎？ 就是每次迭代要額外負擔
→ mistel: 的成本，比方說merge sort每層要花O(n)去切割子問題，或
→ mistel: 者binary search每層要花O(1)去檢查mid是否等於key
原來是這個意思 感謝
※ 編輯: ching4562 (123.193.248.215 臺灣), 12/13/2019 19:59:47
→ mistel: 啊不好意思 merge sort是合併子問題花O(n)才對 打錯了