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

看板Grad-ProbAsk作者 (monster710623)時間6年前 (2019/12/13 17:35), 6年前編輯推噓1(1推 0噓 3→)
留言4則, 1人參與, 6年前最新討論串1/1
https://i.imgur.com/8enKBhQ.jpg
問一下 像這種遞迴是有必要寫出來嗎 像我就寫不太出來紅色框起來的部分 然後就無從判斷起了 像這題也是 問一下怎解 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.200.215.242 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1576229730.A.FA6.html
推
12/13 17:53, 6年前 , 1F
題目不是說overhead是O(n)了嗎？ 就是每次迭代要額外負擔
12/13 17:53, 1F
→
12/13 17:53, 6年前 , 2F
的成本，比方說merge sort每層要花O(n)去切割子問題，或
12/13 17:53, 2F
→
12/13 17:53, 6年前 , 3F
者binary search每層要花O(1)去檢查mid是否等於key
12/13 17:53, 3F
原來是這個意思 感謝 ※ 編輯: ching4562 (123.193.248.215 臺灣), 12/13/2019 19:59:47
→
12/14 12:04, 6年前 , 4F
啊不好意思 merge sort是合併子問題花O(n)才對 打錯了
12/14 12:04, 4F
‣ 更多 ching4562 的文章
文章代碼(AID): #1TyrjY-c (Grad-ProbAsk)