作者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/cn.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