渐进性分析和算法复杂度

2020-07-08 本文已影响0人闪电侠悟空

曲线的渐近线

渐近线是曲线的一种性质，描述曲线在很远位置处的表现，属于高中课本知识;
通常是用直线 $y = g(x)$ 来描述曲线 $y= f(x)$ 在远处的性质; 也就是曲线 $f(x)$ 在很远处和直线 $f(x)$ 基本重合，（不严格的）数学上是: $\lim_{x\rightarrow +\infty} [f(x)-g(x)]\rightarrow 0$
问题：不是所有的曲线 $f(x)$ 都有直线的渐近线, 比如 $f(x)=x^2+x$ 。

https://www.bilibili.com/video/BV1c741137Wf?from=search&seid=13836527270049512517

也是研究曲线 $f(x)$ 在很远处的表现，不过想用简单曲线逼近复杂曲线。看上图， $T_1(n)$ 即使乘以系数 $1.1$ ，按照渐近线定义的绝对距离也没法收敛，不能继续工作了，所以只能退而求其次，采用数量级上的分析。
通常是用简单曲线 $y = g(x)$ 来描绘曲线 $y= f(x)$ 在数量级上的表现; 数学上用: $\lim_{x\rightarrow +\infty} [\frac{f(x)}{g(x)}]$ 来度量。出现数量级上的三种比较结果（大，小，相等）。参考https://blog.csdn.net/chieryu/article/details/50432699
Big O, $O$ , 表示上界。用 $\lim_{x\rightarrow +\infty} [\frac{f(x)}{g(x)}]\rightarrow0$ （数量级上 $f(x)$ 大）或者 $\lim_{x\rightarrow +\infty} [\frac{f(x)}{g(x)}]\rightarrow c, c\neq0$ （数量级上 $f(x)$ 与 $g(x)$ 相同）表示函数 $f(x)$ 在很远处的数量级上的上界是 $g(x)$ 。这种表示太啰嗦，所以大家规定出记号。 $f(x)=O(g(x))$ , 上界.
类似，还有下界 $\Omega$ , $f(x)=\Omega(g(x))$ 。如果既是上界，又是下界，我们就可以说确界(或者紧界)关系 $f(x)=\Theta(g(x))$ .
在算法复杂度分析中，通常有 $O(n),O(n^2),O(nlog(n))$ ,等等。