作者qwer911 (lalalalalala)
看板Grad-ProbAsk
标题[理工] 演算法 105交大
时间Mon Dec 18 11:30:02 2017
http://i.imgur.com/3cDC5du.jpg
想请问像这样的递回程式
要如何转换成
递回关系式
-----
Sent from JPTT on my Asus ASUS_Z017DA.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.51.170.192
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1513567804.A.729.html
1F：推 hank292: 可以看它subproblem的size，这一题的参数会变动只有low和 12/18 12:18
2F：→ hank292: high 12/18 12:18
3F：推 hank292: 而且subproblem一次只有一种会执行，第一个是base case， 12/18 12:20
4F：→ hank292: 另两个会递回 12/18 12:20
5F：推 hank292: 所以可表示为T(N)=T(N/2)+O(1) 12/18 12:22
6F：→ hank292: 其实就是binary search 12/18 12:23