渐进估计与阶
贡献者： int256
这里介绍大 $\mathcal O$ 符号、小 $\mathcal o$ 符号、$\asymp$、$\prec$、$\succ$ 等符号的意义。
对于自变量 $x$ 与其的函数 $f(x)$ 和其总正的函数 $\varphi(x)$。
- $f=\mathcal O(\varphi)$ 表示存在一个足够大的常数 $A$ 使得对于任意 $x$ 总有 $|f(x)| < A \varphi(x)$。
- $f = \mathcal o(\varphi)$ 表示 $f/\varphi \rightarrow 0$。
- $f \sim \varphi$ 表示 $f / \varphi \rightarrow 1$。
例如当 $x \rightarrow +\infty$ 时有
\begin{equation}
\begin{matrix}
10x = \mathcal O(x), &\sin x = \mathcal O(x), &x = \mathcal O(x^2), ~\\
x = \mathcal o(x^2), &\sin x = \mathcal o(x), &x + 1 \sim x ~.
\end{matrix}
\end{equation}
而当 $x \rightarrow 0$ 时有
\begin{equation}
x^2 = \mathcal O(x), ~ x^2 = \mathcal o(x), ~ \sin x \sim x , ~ 1+x \sim 1 ~.
\end{equation}
下面介绍 $\asymp$、$\prec$、$\succ$ 这三个符号。
- $f \prec \varphi$ 表示 $f/\varphi \rightarrow 0$，即 $f = \mathcal o(\varphi)$。
- $f \succ \varphi$ 表示 $f/\varphi \rightarrow \infty$。
- $f \asymp \varphi$ 表示存在正常数 $A$ 与 $B$ 使得 $A\varphi < f < B \varphi$。这又称 $f$ 与 $\varphi$ 同阶。
特别的，$f \sim \varphi$ 等价于 $f = \varphi + \mathcal o(\varphi)$，或 $f = (1 + \mathcal o(1))\varphi$。
另外，在数论中我们说几乎所有数都有某性质 $P$，是指若小于 $x$ 的满足性质 $P$ 的数的个数为 $Q(x)$，则当 $x \rightarrow +\infty$ 时 $Q(x) \sim x$。
在估计阶和渐进时，常用 $A$ 表示待定常数，但特别的，$A$ 之间可以互不相等，而仅用 $A$ 来表示某常数从而证明或估计阶。