→ yauhh:這樣更錯,你直接把遞迴呼叫的工作時間拿掉, 118.167.55.99 10/10 08:44
→ yauhh:看起來很奇怪 118.167.55.99 10/10 08:44
→ yauhh:哦哦,原來是講改寫程式,批錯了,抱歉抱歉. 118.167.55.99 10/10 09:05
※ 引述《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
: }
: 請問這個程式的複雜度是多少?
看到我都複雜起來惹^^
: 應該怎麼改成比較好的寫法呢?
: 謝謝
如果我沒有誤會甚麼的話
先假設 p = [3, 4, 2, 7]; 也就是 4-element
Q3(p, 0) = 0;
Q3(p, 1) = 3;
Q3(p, 2) = Max(3 + 3, 4 + 3);
Q3(p, 3) = Max(3 + 7, 4 + 7, 2 + 7);
Q3(p, 4) = Max(3 + 11, 4 + 11, 2 + 11, 7 + 11);
0, 3, 7, 11 各為 Q3(p, n - 1) 的回傳值
簡單的說目前索引的值只要直接和之前比較過的最大值再比較就可以了
n = 1 時的數值是 3 ，索引只有一個不解釋
取 3 的值來做加總
n = 2 時的數值是 4 ，拿 4 和 n = 1 時的最大值做比較，前者比較大
所以取前者的值 4 來做加總
n = 3 時的數值是 2 ，拿 2 和 n = 2 時的最大值做比較，後者比較大
所以取後者的值 4 來做加總
n = 4 時的數值是 7 ，拿 7 和 n = 3 時的最大值做比較，前者比較大
所以取前者的值 7 來做加總
所以 n = 4 時的答案會是 3 + 4 + 4 + 7
遞迴應該很容易寫，O(n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.42.128.123