作者seika555 (kakkoii)
看板Grad-ProbAsk
标题[理工]资节递回问题
时间Sat Aug 11 00:30:22 2018
https://imgur.com/p5WIr96.jpg
上图题目第一小题的divide and conquer 的观念我还可以理解
但第二小题写成递回式我就不太懂了
我知道有2*T(n/2)但是後面的加T(n-1) + θ(1) 是怎麽来的压
还请大大们帮忙解惑 谢谢
--
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 122.116.213.244
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1533918628.A.35D.html
1F：推 henry78925: 你要计算time comp，其实你去想第一层就好 试想第一层08/11 01:23
2F：→ henry78925: 是拆成两个一半的A丢进递回，2T(n/2) 接着判断A[m]、A08/11 01:23
3F：→ henry78925: [j] θ(1)，最後递回(A,i,j-1)→T(n-1)。08/11 01:23
4F：→ henry78925: 标点符号打的有点烂，将就点谢谢08/11 01:24
谢谢he大，第一层是指递回开始的第一round 吗
因为常常看到题目就实际拿数字带，想很久，所以是每题都可以这样想吗？
※ 编辑: seika555 (114.137.58.189), 08/11/2018 15:05:43
5F：推 henry78925: 对的因为当你写T(n)=aT(n/b) 的形式，递回的部分aT(n/08/11 16:50
6F：→ henry78925: b)这就会帮你递回下去了，所以只要第一层正确，就会是08/11 16:50
7F：→ henry78925: 对的。08/11 16:50
我懂了 谢谢h大
※ 编辑: seika555 (114.137.185.127), 08/11/2018 17:57:36