3.函数的增长

3.1 渐进记号

3.1.1 $\mathrm{\Theta }$ 记号

用于描述函数渐近紧确界的数学符号，同时给出函数的上界和下界，表示函数在足够大的输入规模下 的精确增长趋势。

1. 定义： 对于函数 $f(n)$ 和 $g(n)$ ，若存在正常数 $c_1$，$c_2$ 和 $n_0$ ，使得所有 $n\ge n_0$ 满足：

$$c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$$

则称 $f(n)$ 是 $g(n)$ 的渐近紧确界，记作：

$$f(n)=\mathrm{\Theta }(g(n))$$

2. 直观理解：

• 上下界同时存在： $\mathrm{\Theta }$ 记号表示 $f(n)$ 的增长速度，既不会快于 $g(n)$ 的某个倍数， 也不会慢于 $g(n)$ 的某个倍数。
• 排除低阶项： 例如，若 $f(n)=3n^2+2n+1$ ，则$f(n)=\mathrm{\Theta }(n^2)$，因为当 $n$ 足够大时， $n^2$ 主导了整体增长。

3.1.2 $O$ 记号

用于描述函数渐近上界的数学符号，表示函数在足够大的输入规模下的最坏增长趋势。

1. 定义： 对于函数 $f(n)$ 和 $g(n)$ ，若存在正常数 $c$ 和 $n_0$ ，使得所有 $n\ge n_0$ 满足：

$$f(n)\le c\cdot g(n)$$

则称 $f(n)$ 是 $g(n)$ 的渐近上界，记作：

$$f(n)=O(g(n))$$

2. 直观理解： $O$ 记号表示 $f(n)$ 的增长速度，不会快于 $g(n)$ 的某个倍数。
3. 核心特点：
   • 忽略低阶项： 同$\mathrm{\Theta }$ 记号，$O$ 记号也忽略低阶项。
   • 隐藏常数因子： $O$ 记号通常不关心具体常数（例如， $2n$ 和$100n$ 均为 $O(n)$）。
   • 非紧确上界： $O$ 记号允许上界比实际增长更宽松（例如，$f(n)=n$ 既是 $O(n)$ 也是 $O(n^2)$）。

3.1.3 $\mathrm{\Omega }$ 记号

用于描述函数渐近下界的数学符号，表示函数在足够大的输出规模下的最佳增长趋势。帮助我们理解 算法在最优情况或平均情况下的最优效率，与 $O$ （上界）记号形成互补。

1. 定义： 对于函数 $f(n)$ 和 $g(n)$ ，若存在正常数 $c$ 和 $n_0$ ，使得所有 $n\ge n_0$ 满足：

$$c\cdot g(n)\le f(n)$$

则称 $f(n)$ 是 $g(n)$ 的渐近下界，记作：

$$f(n)=\mathrm{\Omega }(g(n))$$

2. 直观理解： $\mathrm{\Omega }$ 记号表示 $f(n)$ 的增长速度至少为 $g(n)$ 的某个倍数 $c$。关注的是最优情况 或平均情况下的增长趋势。
3. 核心特点：
   • 忽略低阶项： 同$\mathrm{\Theta }$ 记号，$\mathrm{\Omega }$ 记号也忽略低阶项。
   • 隐藏常数因子： 同$O$记号， $\mathrm{\Omega }$ 记号也不关心具体常数。
   • 非紧确下界： $\mathrm{\Omega }$ 记号允许下界比实际增长更宽松（例如，$f(n)=n$ 既是 $\mathrm{\Omega }(n)$ 也是 $\mathrm{\Omega }(n^2)$）。

3.1.4 总结

三者为包含关系：

$$\Omega (g(n))\subseteq \Theta (g(n))\subseteq O(g(n))$$

记号	名称	约束条件	直观理解	示例
$O$	Big-O	$f(n)\le c\cdot g(n)$	最多增长到($\le$)	$3(n^2)=O(n^2)$
$\mathrm{\Omega }$	Big-Omega	$f(n)\ge c\cdot g(n)$	至少增长到($\ge$)	$3(n^2)=\mathrm{\Omega }(n^2)$
$\mathrm{\Theta }$	Big-Theta	$c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$	精确增长到($=$)	$3(n^2)=\mathrm{\Theta }(n^2)$