渐进估计与阶
贡献者： 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$ 来表示某常数从而证明或估计阶。
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。