匿名使用者
匿名使用者 發問時間: 電腦與網際網路程式設計 · 1 0 年前

時間複雜度的問題

因為上課不太懂,就到知識+查了一下

發現

http://tw.knowledge.yahoo.com/question/question?qi...

http://tw.knowledge.yahoo.com/question/question?qi...

這兩個時間複雜度的算法差不多,可是怎麼一個是O(2^n) 一個是 O(n)

不知道是哪一個錯,還是都對?

程式明明差不多阿 .. 都是 遞迴 類似 f(n-x) + f(n-x)

真的很難阿.. 誰來教教我xD

上網看很多的範例 似懂非懂的 ..

1 個解答

評分
  • Leslie
    Lv 7
    1 0 年前
    最佳解答

    第一個網頁沒問題, 直接用遞迴做是 O(2^n),

    若不用遞迴, 而是從頭一項一項往後推,

    每一項只要兩個加, 則是線性的 O(n).

    第貳個網頁應該是打字有誤,

    直接用遞迴仍然是 O(2^n), 其回答中的式子應該是如下才對:

    T(g(n)) = 2T(g(n-1))

    = 2(2T(g(n-2)))

    = ... ... ... ... ...

    = 2^nT(g(n-n))

    = 2^nT(g(0)), T(g(0)) = 1

    = 2^n

    故為 O(2^n).

    當然, 若不用遞迴, 而是從 f(1)=1 , f(2)=2 , f(3)=3 , f(4)=5,

    一項一項往後推, 每一項只要兩個乘, 及一個加, 則是線性的 O(n).

還有問題?馬上發問,尋求解答。