笔记—算法的时间复杂度

发表于 算法 2016-12-20 阅读数: 221

对于一个算法,首先我们要进行两项分析。第一,自然是算法的正确性,第二,则是算法时间复杂度。一个算法花费的时间与算法中语句的执行次数成正比例。一个算法中的语句执行次数称为语句频度或时间频度,记为T(n)。

由于n是问题的规模大小,当n不断地变化时,时间频度T(n)也会不断的变化,我们希望研究T(n)变化的规律。于是引入时间复杂度。

时间复杂度:反映程序执行时间随输入规模增长而增长的量级。若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

T(n)=O(f(n)) 简单来说,就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。由于指数的影响很大,所以当函数里同时有多次方项时,取高次。常数什么的都可以忽略,只取影响最大的部分。就如一条河流有许多分支,我们只取主干流。如:O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 )

若语句执行次数为一个常数,则时间复杂度为O(1),另外时间频度不相同时,时间复杂度可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

时间复杂度

常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)。

那么怎么判断一个算法的时间复杂度呢?

1.找出算法中执行次数最多的那条语句(一般是最里层的循环).

2.计算该语句的执行次数数量级(最高次幂),可以忽略所有系数、常数。

3.将基本语句执行次数的数量级放入大Ο记号中。PS:如果算法中存在并列的循环,就将这两个循环的时间复杂度相加。

如:O(n)

时间复杂度

O(n*n) = O(n^2)

时间复杂度

并列的循环(O(nn+nn) = O(2*n^2)(系数去掉) = O(n^2))

时间复杂度

需要注意的是,我们默认n是趋于无穷的。如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。若语句的执行和问题规模n无关,则应都视为O(1)。

Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者(即多项式时间复杂度的算法)是有效算法,把这类问题称为P(Polynomial,多项式)类问题,而把后者(即指数时间复杂度的算法)称为NP(Non-Deterministic Polynomial, 非确定多项式)问题。对于P和NP我们有这样不严谨而简单的解释:P:算起来比较快的问题,可以叫人接受的。NP:算起来不一定快,但对于任何答案我们都可以快速的验证这个答案对不对。

下面是常用算法的时间复杂度(点击查看大图)。

时间复杂度

欢迎关注微信公众号:幻象客

幻象客 二维码

Add comment