Big-Theta 表示法

與 Big-O 表示法不同，Big-O 表示法僅表示某些演算法的執行時間的上限，Big-Theta 是一個緊密的界限; 上下限。緊束縛更精確，但也更難計算。

Big-Theta 符號是對稱的：f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))

掌握它的直觀方法是 f(x) = Ө(g(x)) 意味著 f(x) 和 g(x)的圖形以相同的速率增長，或者圖形’表現’類似於足夠大的 x 值。 (f(x)) Big-Theta 表示法的完整數學表示式如下：
Ө(f(x))= {g：N 0 - > R 和 c 1 ，c 2 ，n 0 > 0，其中 c 1 <abs（g( n)/ f(n))，對於每個 n > n0 和 abs 是絕對值}

一個例子

如果輸入 n 的演算法需要 42n^2 + 25n + 4 操作完成，我們說這是 O(n^2)，但也是 O(n^3) 和 O(n^100)。然而，它是Ө(n^2) 並且它不是Ө(n^3)，Ө(n^4) 等。雖然Ө(f(n)) 的演算法也是 O(f(n))，但反之亦然！

正式的數學定義

Ө(g(x)) 是一組函式。

Ө(g(x)) = {f(x) such that there exist positive constants c1, c2, N such that 0 <= c1*g(x) <= f(x) <= c2*g(x) for all x > N}

因為Ө(g(x)) 是一個集合，我們可以寫 f(x) ∈ Ө(g(x)) 來表示 f(x) 是Ө(g(x)) 的成員。相反，我們通常會寫 f(x) = Ө(g(x)) 來表達相同的概念 - 這是常見的方式。

每當Ө(g(x)) 出現在公式中時，我們都會將其解釋為代表一些我們無需指定的匿名函式。例如，方程 T(n) = T(n/2) + Ө(n)，意思是 T(n) = T(n/2) + f(n)，其中 f(n) 是集合Ө(n) 中的函式。

讓 f 和 g 是在實數的某個子集上定義的兩個函式。我們把 f(x) = Ө(g(x)) 寫為 x->infinity 當且僅當有正常數 K 和 L 以及實數 x0 這樣的時候：

所有 x >= x0 的 K|g(x)| <= f(x) <= L|g(x)|。

定義等於：

f(x) = O(g(x)) and f(x) = Ω(g(x))

一種使用限制的方法

如果 limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) 即限制存在並且它是正的，那麼 f(x) = Ө(g(x))

常見的複雜性類