渐近分析

渐近分析（asymptotic analysis、asymptotics），在数学分析中是一种描述函数在极限附近的行为的方法。有多个科学领域应用此方法。例子如下：

• 在计算机科学中，算法分析考虑给定算法在输入非常大的数据集时候的性能。
• 当实体系统的规模变得非常大的时候，分析它的行为。

最简单的例子如下：考虑一个函数${\displaystyle f(n)}$，我们需要了解当${\displaystyle n}$变得非常大的时候${\displaystyle f(n)}$的性质。

令${\displaystyle f(n)=n^{2}+3n}$，在${\displaystyle n}$特别大的时候，第二项${\displaystyle 3n}$比起第一项${\displaystyle n^{2}}$要小很多。

于是对于这个函数，有如下断言：“${\displaystyle f(n)}$在${\displaystyle n\rightarrow \infty }$的情况下与${\displaystyle n^{2}}$渐近等价”，记作${\displaystyle f(n)\sim n^{2}}$。

渐近等价

定义：给定关于自然数${\displaystyle n}$的复函数${\displaystyle f}$和${\displaystyle g}$，

命题${\displaystyle f(n)\sim g(n){\mbox{ }}(n\rightarrow \infty )}$表明（使用小o符号）

${\displaystyle f(n)=g(n)+o(g(n)){\mbox{ }}(n\rightarrow \infty )}$

或（等价记法）

${\displaystyle f(n)=(1+o(1))g(n){\mbox{ }}(n\rightarrow \infty )}$。

这说明，对所有正常数${\displaystyle \epsilon }$，存在常量${\displaystyle N}$，使得对于所有的${\displaystyle n\geqslant N}$有

${\displaystyle |f(n)-g(n)|\leqslant \epsilon |g(n)|}$。

当${\displaystyle g(n)}$不是0或者趋于无穷大时，该命题可等价记作

${\displaystyle \lim _{n{\rightarrow }\infty }{\frac {f(n)}{g(n)}}=1}$。

渐近等价是一个关于${\displaystyle n}$的函数的集合上的等价关系。非正式地，函数${\displaystyle f}$的等价类包含所有在极限情况下近似等于${\displaystyle f}$的函数${\displaystyle g}$。

渐近展开

主条目：渐近展开

函数${\displaystyle f(x)}$的渐近展开是它的一种级数展开。这种展开的部分和未必收敛，但每一个部分和都表示${\displaystyle f(x)}$的一个渐近表示式。例子：斯特灵公式。

相关条目

• 渐近运算复杂度（英语：Asymptotic computational complexity）
• 渐近理论（英语：Asymptotic theory）

参考注释

外部链接

• J. P. Boyd, "The Devil's Invention: asymptotic, superasymptotic and hyperasymptotic series", Acta Applicandae Mathematicae, 56: 1-98 (1999). Preprint （页面存档备份，存于互联网档案馆）.