渐进记号总结 & 《算法导论》 3.1
用来描述算法渐进运行时间的记号根据定义域为自然数集 $\mathbb{N}$ 的函数来定义。
这样的记号对描述最坏情况运行时间的函数 $T(n)$ 是方便的。
紧渐进界记号 $\Theta$
断句：紧 渐进 界 记号
upd. 还是叫 紧确渐进界记号 $\Theta$ 比较好..
例子 $f(n) = 3n^2-n+5 = \Theta(n^2)$
定理1：对于任意两个函数 $f(n)$ 和 $g(n)$ ，我们有 $f(n)=\Theta(g(n))$ ，当且仅当 $f(n)=O(g(n)) \land f(n) = \Omega(g(n))$
或者等价的表示为： $\Theta(f(n)) = O(n) \cap \Omega(n)$
证明：显然。$O,\Omega$ 记号的定义详见下文。
渐进上界记号 $O$
一般也写做 $\mathcal{O}$ 。
例子：$f(n) = 2n^2 + 3n + 1 =O(n^2),~f(n) = 2n = O(n^2)$ 。
渐进下界记号 $\Omega$
例子：$f(n) = 2n+3 = \Omega(n),~f(n) = n^3 + 1 = \Omega(n)$ 。
非渐进紧确上界记号 $o$
断句：非渐进紧确 上界 记号
也叫 非紧上界记号 $o$ 。
注意区分大小写。
这等价于
例子： $f(n) = n \log_2 n = o(n^2)$
但是 $f(n) = n^2 -n \ne o(n^2)$ 。因为 $n^2 - n = O(n^2)$ 是渐进紧确的。
非渐进紧确下界记号 $\omega$
断句：非渐进紧确 下界 记号
也叫 非紧下界记号 $\omega$ 。
注意这是 omega ，不是 w
这等价于
例子：$f(n) = n^{\frac{5}{4}} = \omega(n)$
但是 $f(n) = n^4 +1 \ne \omega (n^4)$ ，因为 $n^4 = \Omega (n^4)$ 是渐进紧确的。
渐进记号的性质与比较
| 记号 | 含义 | 通俗理解 |
|---|---|---|
| $\Theta$ | 紧渐进界 | $=$ |
| $O$ | 渐进上界 | $\le$ |
| $o$ | 非紧上界 | $<$ |
| $\Omega$ | 渐进下界 | $\ge$ |
| $\omega$ | 非紧下界 | $>$ |
传递性
自反性
对称性
转置对称性
若 $f(n) =o(g(n))$ ，则称 $f(n)$ 渐进小于 $g(n)$
若 $f(n) = \omega(g(n))$ ，则称 $f(n)$ 渐进大于 $g(n)$
无三分性
指实数的三分性不适用于渐进记号。
实数的三分性：对于任意两个实数 $a,b$ ，下列三种情况必有一种必须成立。
虽然任意两个实数可以进行比较，但是不是所有函数都可以渐进比较。
也就是说，对于两个函数 $f(n)$ 和 $g(n)$
也许 $f(n)=O(g(n))$ 或 $f(n) = \Omega(g(n))$ 都不成立。
书上的例子：
因为 $-1 \le \sin x \le 1$
所以 $g(n)$ 中的幂值在 $0$ 到 $2$ 之间摆动，取介于两者之间的所有值。
参考文献：
[1] https://blog.csdn.net/qq_44575910/article/details/119253189
