计算时间复杂度

关于时间复杂度的计算,看过《算法导论》的人肯定记得那三大方法:“代入法、递归树法、主方法”。那些没有详细研究过的人就很尴尬了(比如我),只能通过较为简单的方法去计算。

因此,本文研究计算时间复杂度的简单方法。水平有限,如有不足,请多多交流。

 

一、《数据结构(C语言版)》中的例子

本流程基于《数据结构(C语言版)》第12页的例1.4。

(1)算法的执行时间和语句的频度

一个算法的执行时间大致上等于其所有语句执行时间的总和,而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。

一条语句的重复执行次数被称为语句的频度。

由于语句的执行要有源程序经编译程序翻译成目标代码、目标代码经装配在执行,因此语句执行一次实际所需的具体时间是与机器的软硬件环境(如机器速度、编译程序质量等)密切相关。所以,所谓的算法分析并非精确统计算法实际执行所需时间,而是针对算法中语句的执行次数做出估计,从中得到算法执行时间的信息。

假设每条语句执行一次所需时间均是单位时间,一个算法的执行时间就是该算法中所有语句的频度之和。

以此算法为例:

TestSimpleExample.java

算法中所有语句的频度之和,即算法的执行时间,用T(n)表示

T(n) = (n+1) + n*(n+1) + n^2 + n^2*(n+1) + n^3 ,结果为:

T(n) = 2*n^3 + 3*n^2 + 2*n + 1

我的理解和书上有点出入。我理解的频度计算如下:

TestSimpleExample.java

T(n) = (n+1) + (n+1)^2 + (n+1)^2 + (n+1)^3 + (n+1)^3 ,结果为:

T(n) = T(n) = 2*n^3 + 8*n^2 + 11*n + 5

但是到最后计算时间复杂度时没有区别,所以关系不大(幂次没有差别,对时间复杂度没什么影响。书上的例子应该是简化版本)。

(2)问题规模和算法的时间复杂度

算法求解问题的输入量成为问题的规模,一般用整数n表示。

问题规模n对不同的问题含义不同。例如,矩阵乘积问题的规模是矩阵的阶数(上面的例子就是矩阵乘积问题,n就是循环的次数),多项式运算问题的规模是多项式的项数,一个图论问题的规模则是图中的顶点数或边数,集合运算问题的规模是集合中元素的个数。

在上面的例子中,T(n) = 2*n^3 + 3*n^2 + 2*n + 1,当n趋向于∞,显然有如下极限:

lim(T(n)/n^3) = lim(2*n^3 + 3*n^2 + 2*n + 1)/n^3 = 2

当n趋向于∞,T(n)和n^3之比是一个不等于0的常数,即T(n)和n^3是同阶的,或者说T(n)和n^3的数量级相等。在这里,我们使用“O”来表示数量级,即:

T(n) = O(n^3)

这就是此算法(矩阵乘积算法)的渐进时间复杂度(就是平时所说的时间复杂度)。

我们可以给出如下概念:

一个算法的时间复杂度是该算法的执行时间,记作T(n),T(n)是该算法所求解问题规模n的函数。当问题的规模n趋向于∞时,T(n)的数量级称为算法的“渐进时间复杂度”,记作:T(n) = O(f(n))。它表示随着问题规模n的扩大,算法执行时间的增长率和f(n)的增长率相同,简称为时间复杂度。

下面是重点:

这的f(n)一般是算法中最大的时间频度,一般情况下是最深层循环内的语句频度。在本例中,f(n)就是:

的时间频度,f(n) = n^3。

(3)我对一些例子的理解

1.交换x和y的值

TestSimpleExample.java

三条语句的频度均为1,算法的执行时间是一个与问题规模n无关的常数,所以算法的时间复杂度为常数阶,记作T(n) = O(1)。

实际上,如果算法的执行时间不随着问题规模n的增加而增长,算法中语句的频度就是某个常数。即使这个常数再大,算法的时间复杂度都是O(1)。

2.变量计数之一

TestSimpleExample.java

对循环语句只需要考虑循环体中语句的执行次数。以上程序段中频度最大的语句是:

其频度为f(n) = n^2,所以该程序段的时间复杂度为T(n) = O(n^2):

3.变量计数之二

TestSimpleExample.java

此算法比较难计算T(n),但是我们知道此程序段中频度最大的语句为x++,从而可以估算T(n)中最高幂次为3(即存在n^3),必定与n^3同阶。因此我们可以估计时间复杂度为T(n) = O(n^3)。

4.顺序查找

TestSimpleExample.java

这里的时间复杂度不仅和问题规模n(即num.length)有关,还与数组num中的元素、查询的元素n有关。

如果要查找的n正好是数组num中的第一个(问题数据的初始状态),那么return的频度为f(n) = 1,时间复杂度为T(n) = O(1)。

如果要查找的n是数组num中的最后一个(问题数据的初始状态),那么循环不得不遍历整个数组,return的频度为f(n) = n,时间复杂度为T(n) = O(n)。

总之,如果某算法的时间复杂度与问题数据的初始状态有关,需要考虑的最坏情况。上面的例子中最坏情况就是“n是数组num中的最后一个”,所以遍历数组的时间复杂度为T(n) = O(n)。

二、归纳时间复杂度的计算方法

参考:http://www.jianshu.com/p/99bac69fdd97

(1)根据定义计算

1. 计算基本操作的执行次数T(n)

基本操作即算法中的每条语句,计算每条语句的执行次数(频度),最后计算频度的总和(T(n))。在做算法分析时,一般默认为考虑最坏的情况。

2. 计算T(n)的数量级

忽略常量、低次幂和最高次幂的系数,计算T(n)的数量级。令f(n)=T(n)的数量级(此处的f(n)为执行次数最多的语句的频度)。

3. 用大O来表示时间复杂度

当n趋近于无穷大时,如果lim(T(n)/f(n))的值为不等于0的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。得到时间复杂度。

(2)简化步骤

1. 找到执行次数最多的语句

直接看哪条语句执行次数最多,找到该条语句即可。

2. 计算该语句执行次数的数量级

简单计算语句的执行次数,取最高次幂(比如T(n) = 2*n^3 + 3*n^2 + 2*n + 1,最高次幂为n^3)。

3. 用大O来表示结果

直接得到结果:T(n) = O(n^3),和计算出来的结果一模一样。

这种计算方法存在一些问题(比较适用于简单算法),当算法复杂的时候最高次幂很难找,还是需要老老实实地计算。

三、总结

概念问题,和数据结构紧密相关,必须掌握。

发表评论

电子邮件地址不会被公开。 必填项已用*标注