大O记法

大O符号(Big O notation)是用于描述函数渐进行为的数学符号。更确切地说,它是用另一个(通常更简单的)函数来描述一个函数数量级的渐近上界。在数学中,它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项;在计算机科学中,它在分析算法复杂性的方面非常有用。

对于算法进行特别具体的细致分析虽然很好,但在实践中的实际价值有限。对于算法的时间性质和空间性质,最重要的是其数量级和趋势,这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如,可以认为3n^2和100n^2属于同一个量级,如果两个算法处理同样规模实例的代价分别为这两个函数,就认为它们的效率“差不多”,都为n^2级。

最坏时间复杂度

分析算法时,存在几种可能的考虑:

算法完成工作最少需要多少基本操作,即最优时间复杂度 算法完成工作最多需要多少基本操作,即最坏时间复杂度 算法完成工作平均需要多少基本操作,即平均时间复杂度

对于最优时间复杂度,其价值不大,因为它没有提供什么有用信息,其反映的只是最乐观最理想的情况,没有参考价值。

对于最坏时间复杂度,提供了一种保证,表明算法在此种程度的基本操作中一定能完成工作。

对于平均时间复杂度,是对算法的一个全面评价,因此它完整全面的反映了这个算法的性质。但另一方面,这种衡量并没有保证,不是每个计算都能在这个基本操作内完成。而且,对于平均情况的计算,也会因为应用算法的实例分布可能并不均匀而难以计算。

因此,我们主要关注算法的最坏情况,亦即最坏时间复杂度。

时间复杂度的几条基本计算规则

1、基本操作,即只有常数项,认为其时间复杂度为O(1)

2、顺序结构,时间复杂度按加法进行计算

3、循环结构,时间复杂度按乘法进行计算

4、分支结构,时间复杂度取最大值

5、判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略

6、在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度

算法的目标编辑

容易理解

编码和调试

优秀的算法通常是简洁而清晰的,这样带来的直接好处就是易于编码和理解,同时这样算法也必定是健壮的,如果一个算法晦涩难懂,则很可能其中会隐藏较多的错误。

最小的代价

算法的代价的最小化是指其执行时间最短且占用的存储空间最少,它们之间 往往是相互矛盾的,然而一般而言,算法的执行时间是主要的评价标准。

2018-05-24 02:18

留言