作者yauhh (哟)
看板Programming
标题Re: [问题] 递回改写, 复杂度
时间Sat Oct 6 00:05:02 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
: }
: 请问这个程式的复杂度是多少?
: 应该怎麽改成比较好的写法呢?
: 谢谢
把执行图画出来大概就感觉得到. 括弧代表一个执行空间,括弧中的数字代表
该范围中的n值. 把 i=1~n 表达成 (i_1)(i_2)(i_3)...(i_n) 这样一列.
也就是整个写起来很像 Lisp 的 list 那样.
Q3(p,1): (1) = ((0))
Q3(p,2): (2) = ((0)((0)))
Q3(p,3): (3) = ((0)((0))((0)((0))))
Q4(p,4): (4) = ((0)((0))((0)((0)))((0)((0))((0)((0)))))
会感觉到是个偏斜树. 那复杂度的算法要算的是这棵树的节点成长量.
应该是 O(n^n).
至於程式打算写什麽,这麽看吧:
当只有一个 p_1 时,就是 p_1.
当 p_2 出现,它先拿到一个 p_1, 然後将 p_1 跟 (p_2 + p_1) 比较,
要嘛 p_1, 要嘛 (p_2 + p_1).
然後, p_3 出现, 如果之前是 p_1 胜出,要嘛 p_1, 要嘛 p_3 + p_1,
否则若之前 (p_2 + p_1) 胜出,要嘛 (p_2 + p_1), 要嘛 p_3 + (p_2 + p_1).
重写的版本大概就这样:
qq3(p,n)
{
if (n==0) return 0
if (n==1) return p[1]
q = qq3(p, n-1)
if (p[n] < q)
return q
return (p[n] + q)
}
然後,回头发现 max(a, b) 没有定义清楚,要再定义一下.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.167.44.50
※ 编辑: yauhh 来自: 118.167.44.50 (10/06 01:08)