1、概念
渐进符号是对算法运行时间的一种估计,而不是精确的时间。使用渐进符号来估计当输入规模变大时,用一个确定的算法来解决一个问题是否可行,这里的可行是指时间上是否可行。
渐进符号有三个,以下为三个渐进符号:
- big-O: 最坏运行时间
- big-Ω:最好运行时间
- big-Θ:介于两者之间,取两者的交集
渐进符号是对算法运行时间区间的度量,他们之间的关系应该是big-Ω<=big-Θ<=big-O。
1.1、为什么是估计而不是精确时间?
一句话总结:精确时间计算太复杂了,不好做。
因为计算精确时间太复杂,主要因素如下(软件和硬件):
- 算法的运行时间依赖于编程语言
- 算法的运行时间依赖于编译器
- 算法的运行时间依赖于处理器或硬件
- 其他因素
以上这些因素会导致评估精确运行时间的复杂性,因为这些因素都是变量,不同的编程语言、编译器、处理器和其他因素对同一算法的代码编写、编译及优化、处理器的执行是不一样的。在算法设计的及分析时,如果需要把所有的编程语言、编译器、处理器和其他因素都考虑进来,那么算法设计及分析就会非常复杂。
基于以上问题,算法设计和分析需要一个常量,这个常量的意思就是:在这个算法中,无论外部环境(编程语言、编译器、处理器和其他因素)如何改变,算法不变的是什么。算法不变的内容是算法时间分析的一个核心。
1.2、算法分析应该关注什么?
一句话总结:主要关注输入大小和输入的增长,其他因素都视为一个常数。
- 函数输入大小
这个比较容易理解,因为如果任何算法的输入只要足够小,那么这些算法的运行时间都很快,所以输入大小是评判一个算法运行时间的重要维度。 - 函数输入的增长
只关注一些固定大小的输入也不行,因为输入一直会改变,会变大会变小,变小了当然好,因为确定的算法可以处理当前不变的大小,那么处理更小的输入肯定没问题。那如果输入一直在变大,变大一直变成无穷大(夸张手法),那么这个确定的算法在这种情况下运行时间是如何改变的的?
看下图(图片来源于:可汗学院)
这张图是对应的函数是
,图中红线的增长趋势远大于蓝线,那么就可以说这个算法的运行时间是n的平方,舍掉了系数6和100n+300两项,之所以可以舍掉这两项是因为我们假设n的数字足够大。什么是足够大?简单把n当成无穷大就可以了。
下图是对n的平台系数的改变的图(图片来源于:可汗学院):
从上图可以看出虽然刚开始的时候红线低于蓝线,但是到达了大概1800及以后,红线的增长趋势开始明显的比蓝线大了,所以常量系数并不影响对增长趋势的评估可以舍弃。
2、big-O 渐进上界
一句话总结:big-O用来描述算法最坏运行时间的,算法的最长运行时间
big-O是对算法最坏运行时间的描述,是为了让人了解算法在一些特殊情况下最大运行的时间。
如果说算法运行时间是O(f(n)),这其实表示在n足够大时,算法的最大运行时间是有一个常量k使得最大运行时间k*f(n)为算法的最大运行时间。
如下图(图片来源于:可汗学院):
2.1、big-O局限性
big-O符号不能提供算法运行时间的下限,所以需要Ω符号。
3、big-Ω 渐进下界
一句话总结:big-O用来描述算法最好运行时间的,算法的最短运行时间
big-Ω是对算法最好运行时间的描述。因为有时候我们想要知道一个算法最小运行时间。
如下图(图片来源于:可汗学院):
3.1、怎么样来理解和计算big-Ω
一些算法可以在一些特殊的输入下在Ω(1)的运行时间内完成,我也可以说这些算法的最小运行时间是Ω(1),但是不精确。
举例:假设你银行卡里有100块钱,那么你说我的银行卡里面最少有1块钱也是对的,但是并不精确。
所以算法在给出Ω时都需要计算出一个尽可能精确的Ω运行时间。
举例:你可以说我的银行卡里面最好有99.999999…块钱或者说我的银行里有100块钱。
4、big-Θ 渐进紧确界
一句话总结:big-Θ既可以描述上界又可以描述下届,其实就是找一个函数,如果把这个函数塞到Ω和O之间就可以了
当用Θ(n)来描述算法运行时间时,Θ (n)表示该算法运行时间为:最小运行时间是k1*n,最大运行时间是k2*n,其中k1和k2是常数。
如下图(图片来源于:可汗学院):
5、总结
- 算法分析时不要考虑一些外部变量,如编程语言、编译器、处理器和其他因素,聚焦于算法本身上的“不变量”
- 在得到算法函数后,可以通过舍弃掉小项和常量系数,来简化表示
- big-O 用来描述最坏运行时间
- big-Ω用来描述最好运行时间
- big-Θ既可以描述最好又可以描述最坏运行时间
6、参考
- 可汗学院https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation
- 离散数学及其应用第六版
- 算法导论 第三版