作者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