Time complexity analysis of algorithms

时间复杂性的计算
一般而言，较小的问题所需要的运行时间通常要比较大的问题所需要的时间少。设一个程序P所占用的时间为T，则
　　　　　　　　T(P)=编译时间+运行时间。

编译时间与实例特征是无关的，且可假设一个编译过的程序可以运行多次而无需再编译。因此分析程序的时间特性就只需考虑程序的运行时间。

令程序P的运行时间为tp(n),其中n是所要求解问题的实例特征。由于编写程序时，影响tp的许多因素还是未知的，所以只能对tp进行估算。
由于代码P的主要操作通常包括加、减、乘、除、比较、读、写等，而这些操作的执行时间是可预知的，从而可用下面的公式计算程序P的运行时间:
　　　　　　　　tp(n)=ca*ADD(n)+cs*SUB(n)+cm*MUL(n)+cd*DIV(n)+…
其中, ca，cs，cm，cd分别表示一个加、减、乘、除操作所需要的时间；函数ADD(n)，SUB(n)，MUL(n)，DIV(n)分别表示程序P中所使用的加、减、乘、除操作的次数。

时间复杂性的计算

(1)操作计数

估算一个程序的时间复杂性的一种方式就是首先选择一种或多种操作(如＋，×或比较等)，然后确定这些操作分别执行的次数，就可以计算出该程序的执行时间。这种方法是否成功取决于识别关键操作(这些操作对时间复杂性的影响较大)的能力。例如：（求最大值）

int Max(int a[],int n){
//在a[0..n-1]中找最大的元素，假设数据元素都是整型数
int pos=0;
for(int i=1;i<n;i++)
if(a[pos]<a[i])
pos=i;
return pos;
}//Max

　我们可以选择元素间的比较操作作为关键操作。显然，a[pos]<a[i]的比较进行了n-1次。但除此之外，循环控制变量与循环终止条件之间也进行了n次比较。当然，初始化操作pos=0以及对循环变量的修改等操作也需要考虑，但这些操作通常只对操作计数的结果增加一个常量。

（2 ）执行步数

　　从关于操作计数的讨论可以看出，利用操作计数方法来估算程序的时间复杂性忽略了所选择操作之外的其它操作的开销，而这些开销的积累值有时较大，毫无疑问会影响到程序的执行时间。在统计执行步数的方法中，将会统计程序在执行过程中的所有时间开销。
　　与操作计数法一样，执行步数也是实例特征的函数，尽管一个特定的程序可能会有若干个特征(如输入个数，输出个数，输入和输出的大小等)，但可以将执行步数看成是其中一部分特征的函数。

定义[程序步]：程序步(program step)可定义为一个语法或语义意义上的程序片段，该片段的执行时间独立于实例特征。

　　由一个程序步所表示的计算量可能与其他形式表示的计算量不同。
例如，下面这条完整语句：
return a+b+b*c+(a+b-c)/(a+b)+4；
　　可以看成是一个程序步，只要它的执行时间独立于所选用的实例特征。也可以把如下语句看成为一个程序步：
x=y；
　　显然，这两个程序步的计算量是不一样。

可以通过创建一个全局变量count(其初值为0)来确定一个程序或函数为完成其预定的任务所需要的执行步数。可以将count引入到程序执行语句之中，每当原始程序中的一条语句被执行时，就为count累加上该语句所需要的执行步数。当程序运行结束时所得到的count的值就是所需要的执行步数。例如：（把计算count引入到求n个数和的程序中）

Void Sum(datatype a[]，int n)
{//求a[0..n-1]中元素之和
datatype tsum=0；
count++； //对应于tsum=0的执行步数
for(int i=0；i<n；i++) {
count++； //对应于for的执行步数
tsum+=a[i]；
count++； //对应于赋值语句的执行步数
}
count++； //对应于for语句的最后一次执行
count++； //对应于return语句的执行步数
return tsum；
}//Sum 当程序运行结束时所得到的count的值就是求和程序的执行步数。可见,该程序的执行步数是2n+3。

计算平均执行步数

为了计算平均执行步数，假定x被插入到任何位置上的概率是一样的，由于共有n+1个可能的插入位置，所以概率为1/(n+1)。如果x最终被插入到j位置处
(j>=0)，则执行步数为2n-2j+3，这是因为在j处插入x时，for语句的循环体执行了n-j次。所以平均执行步数为：
n n
tavgInsert（n）= — Σ(2n-2j+3) = — (2Σk+3(n+1)) = n+3
　　　　　　　　　　j=0 　　　　　　　　k=0

还有好多例子，说明了这个问题，不一一列举，需要多多锻炼，调试才能理解时间复杂度在算法中的具体位置。

Time complexity analysis of algorithms

相关推荐