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