Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

Big Notation 和 master method

我不太清楚,從一個遞迴數列該如何找出theta,只知道t(n) <= O, t(n) >= omega,而theta 在兩者之間,O是直接取最高次項不計係數,omega取小於等於t(n)的最大數。看了幾次都還是不懂,theta難道就是用不等式,符合結果的就是了嗎? 有沒有方法從recursion tree 和遞迴的一般式 看出來呢? 還有,我看了三種歸納法,代入、recursion tree 和master method,雖然沒有到看不懂,但一般寫程式真的有必要做這麼困難的事情嗎? extend master method 就能解所有遞迴式了嗎? 還是有其他類型?

我查了很多地方,大家都說theta代表的意義是O和omega相交的集合,O是最差情況的時間複雜度,而omega反之,所以theta可以解釋成平均時間複雜度嗎? 感覺好像又不太對,我好像之前看過,平均是要把 最差/最佳/普通情況的input連同發生機率一起計算,很複雜..

希望各位高手能回答,指正我的觀念,感謝!

2 Answers

Rating
  • sponge
    Lv 6
    7 years ago
    Favorite Answer

    從您的問題看起來,應該是對這些 notation 代表意義還不甚清楚

    O, Ω, Θ 是 "growth of function", 形容函數當輸入數值上升時輸出結果增加的狀況

    它們要描述的是輸入很大時函數輸出對應輸入的變化

    您問題中的最高次係數只是判斷它們的一個特例

    Θ 顯示的涵義為「對函數輸出變化影響最大的項或因素」

    說 Θ 是 O, Ω 交集,那要先解釋何謂 O, Ω

    O: 函數裏成長一樣或比 T(n) 快者

    Ω: 函數裏成長一樣或比 T(n) 慢者

    那 Θ 就是成長速率與 T(n) 一樣者

    如果 T(n) 能寫成單純 n 的表示,很輕易就看出這些指標

    但面對遞迴關係,最通用的辦法還是將它剖析

    如 T(n) = 2T(n/2) + n, 用 master method 很快就得解 Θ(n lg n)

    (lg 是對數以 2 為底)

    但最一般的方法應該把它逐漸拆解:

    T(n)

    = 2T(n/2) + n

    = 2( 2T(n/4) + n/2) + n

    = 4T(n/4) + n + n

    = 8T(n/8) + n + n + n

    = ... 找出一般式

    = 2^k T(n/2^k) + kn

    = ... 持續直到 T 的參數變為常數來決定 k

    = nT(1) + n lg n, k = lg n

    T(1) 就是常數,nT(1) 是 Θ(n), 其對輸出影響程度不如 n lg n

    因此整體 T(n) 成長取決於後面 Θ(n lg n)

    若懷疑為何非拆解到 1 不可,就用常數 c 改寫:

    = (n/c)T(c) + (lg n/c)n, k = lg n/c

    = (n/c)T(c) + (lg n - lg c)n

    = n( T(c)/c - lg c ) + n lg n

    結論會和 c 無關,都 Θ(n lg n)

    至於從 recursion tree 轉 Θ, 就是計算所有 leaf 的時間

    以上的 kn 就是 k 個 Θ(n) 的 leaf, nT(1) 是一個 Θ(n) leaf

    (extended) master method 只是針對某些特別的遞迴形式歸納速解

    遞迴後面有二項,像 T(n) = T(n-1) + T(n-2)

    則 T(n) = Θ(1.618^n), 1.618 代表黃金比例

    就無法用 (extended) master method

    應用上如果您只想用現成演算法拼湊 App, 當然不用如此複雜

    但研究新演算法就必須靠這些技巧驗證其複雜度

    另外 Θ 不是「平均」時間複雜度

    平均時間複雜度很受輸入數量、類型的機率分布左右

    有相同 O, Ω 不保證一樣的 Θ

    希望以上回答對您有幫助!

  • 7 years ago

    參考下面的網址看看

    http://phi008780430.pixnet.net/blog

Still have questions? Get your answers by asking now.