collin37

從您的問題看起來，應該是對這些 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, Ω 不保證一樣的 Θ

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