Re: [問題] 遞迴改寫, 複雜度
※ 引述《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
→
10/10 08:44, , 1F
10/10 08:44, 1F
→
10/10 08:44, , 2F
10/10 08:44, 2F
→
10/10 09:05, , 3F
10/10 09:05, 3F
討論串 (同標題文章)
完整討論串 (本文為第 3 之 3 篇)：
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
