大 O 和大 Θ 表示法的基础理解与证明示例

Big O 和 Big Θ 是计算机科学中用来描述算法复杂性的符号。它们可以帮助我们理解算法在最坏、最好或平均情况下的性能。

1. Big-O (大O表示法)

Big-O 表示上界，即算法的运行时间或空间复杂性的最坏情况。

要证明 f(n) = O(g(n))，你需要确保存在正常数 ( c ) 和 ( $n_0$ )，使得对于所有 ( $n \geq n_0$ )，都有 ( $f(n) \leq c \times g(n)$ )。

证明例子:

假设 ( $f(n) = 3n^2 + 2n + 5$ )，我们想证明它是 ( $O(n^2)$ )。

选择 ( $c = 6$ ) 和 ( $n_0 = 1$ )。

对于所有的 ( $n \geq 1$ )：

( $f(n) = 3n^2 + 2n + 5$ )

( $\leq 3n^2 + 2n^2 + 5n^2$ )（这里我们故意使每个项都变大）

( $= 10n^2$ )

但 ( $10n^2 \leq 6n^2$ ) 不成立。尝试其他常数，例如 ( $c = 11$ )。

( $f(n) \leq 11n^2$ ) 对于所有 ( $n \geq 1$ ) 是成立的，所以 ( $f(n) = O(n^2)$ )。

2. Big-Θ (大 Theta 表示法)

Big Θ 描述了算法的严格界限。如果 f(n) = Θ(g(n))，这意味着 f(n) 是 O(g(n)) 和 Ω(g(n))（Ω 表示下界）。

要证明 f(n) = Θ(g(n))，你需要确保存在常数 ( $c_1$ )、( $c_2$ ) 和 ( $n_0$ )，使得对于所有 ( $n \geq n_0$ )，都有 ( $c_1 \times g(n) \leq f(n) \leq c_2 \times g(n)$ )。

证明例子:

对于之前的 ( $f(n) = 3n^2 + 2n + 5$ )，我们想证明它是 ( $Θ(n^2)$ )。

已经证明了 ( $f(n) \leq 11n^2$ ) 对于某个常数 ( $c_2$ )。

现在，让我们证明下界。为简单起见，选择 ( $c_1 = 3$ ) 和相同的 ( $n_0 = 1$ )：

对于所有的 ( $n \geq 1$ )：

( $f(n) = 3n^2 + 2n + 5$ )

( $\geq 3n^2$ )（忽略其他较小的项）

因此，对于所有 ( $n \geq 1$ )，有 ( $3n^2 \leq f(n) \leq 11n^2$ )。

所以 ( $f(n) = Θ(n^2)$ )。

总结：大 O 和大 Θ 证明都涉及到为给定的函数选择适当的常数，以确保函数的增长率与我们希望的复杂性类似。大 O 关心上界，而大 Θ 关心上界和下界都匹配给定的复杂性。