渐进等价

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

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

f(n)=g(n)+o(g(n)) (n→ → -->∞ ∞ -->){\displaystyle f(n)=g(n)+o(g(n)){\mbox{ }}(n\rightarrow \infty )}

或（等价记法）

f(n)=(1+o(1))g(n) (n→ → -->∞ ∞ -->){\displaystyle f(n)=(1+o(1))g(n){\mbox{ }}(n\rightarrow \infty )}。

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

|f(n)− − -->g(n)|⩽ ⩽ -->ϵ ϵ -->|g(n)|{\displaystyle |f(n)-g(n)|\leqslant \epsilon |g(n)|}。

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

limn→ → -->∞ ∞ -->f(n)g(n)=1{\displaystyle \lim _{n{\rightarrow }\infty }{\frac {f(n)}{g(n)}}=1}。

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

渐近展开

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

相关条目

渐近运算复杂度（英语：Asymptotic computational complexity）

渐近理论（英语：Asymptotic theory）

参考注释

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。