Re: [問題] 遞迴改寫, 複雜度

[yauhh (喲)]

※ 引述《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
: }
: 請問這個程式的複雜度是多少?
: 應該怎麼改成比較好的寫法呢?
: 謝謝

重解一次: 首先看原式, Q3(p, n-1) 對 Q3(p, n) 是恆定的值,卻被呼叫了n次.
其實可以抽取出來,

    Q3(p, n)
        if n == 0
            return 0
        q = -32767
        q1 = Q3(p, n-1)
        for i = 1 to n
            q = max(q, p[i] + q1)
        return q

然後就解了. 這樣變成 O(n^2), 比原來的 O(n^n) 好得太多.


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 118.167.55.99
→ Lordaeron:你真的好好的去讀一下演算法吧.
→ yauhh:你很煩,一直叫人看書,自己卻不看書
推 dryman:真的是一直叫人看書，超煩
→ bbbing:偷懶一點，好好去把wiki(全部)讀一遍
→ yauhh:再偷懶一點,去書店把書架上的書名瀏覽一遍.