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
: }
: 請問這個程式的複雜度是多少?
: 應該怎麼改成比較好的寫法呢?
: 謝謝
把執行圖畫出來大概就感覺得到. 括弧代表一個執行空間,括弧中的數字代表
該範圍中的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)
討論串 (同標題文章)
完整討論串 (本文為第 1 之 3 篇)：