Yahoo 知識+ 將於 2021 年 5 月 4 日 (美國東岸時間) 停止服務，而 Yahoo 知識+ 網站現已轉為僅限瀏覽模式。其他 Yahoo 資產或服務，或你的 Yahoo 帳戶將不會有任何變更。你可以在此服務中心網頁進一步了解 Yahoo 知識+ 停止服務的事宜，以及了解如何下載你的資料。
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 個解答
- spongeLv 67 年前最愛解答
從您的問題看起來，應該是對這些 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, Ω 不保證一樣的 Θ
希望以上回答對您有幫助！
