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))

常见的复杂性类