在算法分析中，渐进符号用于描述算法在输入规模趋于无穷大时的运行时间或空间增长速率。主要的渐进符号包括 O O O、 Ω \Omega Ω、 Θ \Theta Θ、 o o o 和 ω \omega ω。这些符号各自描述了不同的增长界限，本文给出详细的定义和区别。
渐进符号
1. 大 O O O 符号（Big-O Notation）
- 定义：表示上界，用于描述算法的最坏情况复杂度。
- 意义：如果一个算法的时间复杂度为 T ( n ) = O ( f ( n ) ) T(n) = O(f(n)) T(n)=O(f(n))，意味着当输入规模 n → ∞ n \to \infty n→∞ 时，算法的时间增长不会超过某个常数倍的 f ( n ) f(n) f(n)。
- 形式化定义：存在正数 C C C 和 n 0 n_0 n0，使得对所有 n ≥ n 0 n \geq n_0 n≥n0 有 T ( n ) ≤ C f ( n ) T(n) \leq C f(n) T(n)≤Cf(n)。
- 示例：对于一个冒泡排序算法，其时间复杂度为 O ( n 2 ) O(n^2) O(n2)，表示在最坏情况下的复杂度不会超过 n 2 n^2 n2 量级。
2. 大 Ω \Omega Ω 符号（Big-Omega Notation）
- 定义：表示下界，用于描述算法的最好情况复杂度。
- 意义：如果一个算法的时间复杂度为 T ( n ) = Ω ( f ( n ) ) T(n) = \Omega(f(n)) T(n)=Ω(f(n))，意味着当 n → ∞ n \to \infty n→∞ 时，算法的增长速率至少是 f ( n ) f(n) f(n)<
