渐进估计与阶

贡献者： int256

　　 这里介绍大 $\mathcal{O}$ 符号、小 $\mathcal{o}$ 符号、$\asymp$、$\prec$、$\succ$ 等符号的意义。

　　 对于自变量 $x$ 与其的函数 $f(x)$ 和其总正的函数 $\phi (x)$。

• $f=\mathcal{O}(\phi )$ 表示存在一个足够大的常数 $A$ 使得对于任意 $x$ 总有 $|f(x)|<A\phi (x)$。
• $f=\mathcal{o}(\phi )$ 表示 $f/\phi \to 0$。
• $f\sim \phi$ 表示 $f/\phi \to 1$。

　　 例如当 $x\to +\mathrm{\infty }$ 时有

　　 下面介绍 $\asymp$、$\prec$、$\succ$ 这三个符号。

• $f\prec \phi$ 表示 $f/\phi \to 0$，即 $f=\mathcal{o}(\phi )$。
• $f\succ \phi$ 表示 $f/\phi \to \mathrm{\infty }$。
• $f\asymp \phi$ 表示存在正常数 $A$ 与 $B$ 使得 $A\phi <f<B\phi$。这又称 $f$ 与 $\phi$ 同阶。

　　 特别的，$f\sim \phi$ 等价于 $f=\phi +\mathcal{o}(\phi )$，或 $f=(1+\mathcal{o}(1))\phi$。

　　 另外，在数论中我们说几乎所有数都有某性质 $P$，是指若小于 $x$ 的满足性质 $P$ 的数的个数为 $Q(x)$，则当 $x\to +\mathrm{\infty }$ 时 $Q(x)\sim x$。

　　 在估计阶和渐进时，常用 $A$ 表示待定常数，但特别的，$A$ 之间可以互不相等，而仅用 $A$ 来表示某常数从而证明或估计阶。