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) 中的函式。

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

所有 x >= x0K|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))

常見的複雜性類

名稱 符號 n = 10 n = 100
Constant Ө(1) 1 1
Logarithmic Ө(log(n)) 3 7
Linear Ө(n) 10 100
Linearithmic Ө(n*log(n)) 30 700
Quadratic Ө(n^2) 100 10 000
Exponential Ө(2^n) 1 024 1.267650e + 30
Factorial Ө(n!) 3 628 800 9.332622e + 157