(一)1.1_时间复杂度的计算 - 好文

<>前言

同一个算法用不同的语言实现,或者用不同的语言实现,或者用不同的编译程序进行编译,或者在不同的计算机上运行时,效率均不同.所以用绝对的时间单位衡量算法的效率是不合适的.于是,便引入了时间复杂度这一概念来衡量算法的效率.
一般情况下,算法中的基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记做T(n)=O(f(n))
,它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度.

一.相关概念

(1)时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。
一个算法中的所有语句执行次数之和称为语句频度或时间频度。记为T(n)。

(2)时间复杂度

n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。所以，我们引入时间复杂度概念。
一般情况下，算法中基本操作重复执行的次数(时间频度)
是问题规模n的某个函数，用T(n)表示，若有某个函数f(n),存在一个正常数C使得f(n)*C>=T(n)恒成立,即T(n)与f(n)的增长率相同,则称f(n)是T(n)的同数量级函数。
记作T(n)=Ｏ(f(n)),其中O(f(n))表示算法的渐进时间复杂度,简称时间复杂度,所以T(n)=Ｏ(f(n))表示的意思是:一个时间频度为T(n)的算法它的时间复杂度为O(f(n))
注意:
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n²+4n+3与T(n)=n²+2它们的时间频度不同，但时间复杂度相同，都为O(n²)。

二.时间复杂度的计算
1.举个例子算一下
//求两个n阶矩阵的乘法c=a*b的算法 void MaxtrixMultiply(int n,float a[MAX][MAX],float b[MAX][
MAX],float c[MAX][MAX]) { int i,j,k; //执行频度1 float x; //执行频度1 for(i=1;i<=n;i++)
//执行频度n+1,i=n+1时要进行一次条件判断操作,所以是n+1,下面操作也是同理 { for(j=1;j<=n;j++) //执行频度(n+1)n { x
=0; //执行频度n^2 for(k=1;k<=n;k++) //执行频度(n+1)n^2 x+=a[i][k]*b[k][j]; //执行频度n^3 c[i
][j]=x; //执行频度n^2 } } }
上面这个算法的时间频度T(n)=1+1+n+1+(n+1)n+n²+(n+1)n²+n³+n²=2n³+4n²+2n+3;
由数学知识可知2n³+4n²+2n+3的增长率和n³相同,所以时间复杂度O(f(n))=O(n³)
所以时间频度为T(n)=2n³+4n²+2n+3的算法的时间复杂度为O(n³),记做T(n)=O(n³) .
综上求得上述算法的时间复杂度为T(n)=O(n³)
注意:
上面是对算法中所有语句操作都进行了时间频度的计算,但是通常为了方便快速计算时间频度,而省略声明变量,赋值初始化变量等一些操作的计算,只对算法的主要操作进行计算,这样求得的时间频度虽然不同,但是时间复杂度是相同的.

所以读者不要有疑惑,为什么有的课本或试卷上的解题步骤没有计算算法中的所有语句的时间频度?那是因为只对主要操作进行了计算.因为我们要求的是算法的时间复杂度,那些非主要的操作语句并不会影响算法的时间复杂度,所以我们可以简便计算,只对算法的主要操作语句进行计算.

三.总结

求一个算法的时间复杂度要先求得算法的时间频度,一条语句执行一次,时间频度就是1,执行10次就是10,执行n次就n,而时间频度T(n)可以只对算法的主要语句进行计算,然后找到一个函数f(n),存在一个正常数C使得f(n)*C>=T(n)恒成立,则时间复杂度就是T(n)=O(f(n)),所以怎么快速找到f(n)?只需取T(n)函数中的最高次幂项,系数化为1即可.
例如:
T(n)=2n³+4n²+8n+3中,最高次幂项是2n³,然后系数化为1,f(n)=n³,所以时间复杂度为T(n)=O(n³)
假如T(n)中只有常数项,那么f(n)=1,即时间复杂度是O(1).
例如:T(n)=10,那么f(n)=1,所以时间复杂度为T(n)=O(1).

热门工具换一换