作者yauhh (哟)
看板Programming
标题Re: [问题] 递回改写, 复杂度
时间Tue Oct 9 23:46:10 2012
※ 引述《wsx02 ()》之铭言：
: 原题 http://ppt.cc/-87d
: Q3(p,n)
: {
: if(n==0) return 0
: q = -无穷大
: for(i=1~n)
: q = max( q, p[i]+Q3(p,n-1) )
: retrun q
: }
: 请问这个程式的复杂度是多少?
: 应该怎麽改成比较好的写法呢?
: 谢谢
重解一次: 首先看原式, Q3(p, n-1) 对 Q3(p, n) 是恒定的值,却被呼叫了n次.
其实可以抽取出来,
Q3(p, n)
if n == 0
return 0
q = -32767
q1 = Q3(p, n-1)
for i = 1 to n
q = max(q, p[i] + q1)
return q
然後就解了. 这样变成 O(n^2), 比原来的 O(n^n) 好得太多.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.167.55.99
1F：→ Lordaeron:你真的好好的去读一下演算法吧. 1.162.23.179 10/09 23:48
2F：→ yauhh:你很烦,一直叫人看书,自己却不看书 118.167.55.99 10/09 23:51
3F：推 dryman:真的是一直叫人看书，超烦 114.45.175.53 10/10 09:01
4F：→ bbbing:偷懒一点，好好去把wiki(全部)读一遍123.110.134.140 10/14 11:49
5F：→ yauhh:再偷懒一点,去书店把书架上的书名浏览一遍. 118.167.49.206 10/14 12:42