Re: [問題] 遞迴改寫, 複雜度

看板Programming作者yauhh (喲)時間11年前 (2012/10/09 23:46)推噓1(1推 0噓 4→)

留言5則, 4人參與討論串2/3 (看更多)

※ 引述《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

→

Lordaeron

10/09 23:48, , 1^F

10/09 23:48, 1^F

→

yauhh

10/09 23:51, , 2^F

10/09 23:51, 2^F

推

dryman

10/10 09:01, , 3^F

10/10 09:01, 3^F