常用算法时间复杂度的计算方法

时间:2022-06-02 17:10:05

1. 时间复杂度

  时间复杂度是指程序运行从开始到结束所需要的时间。时间复杂度的计算一般比较麻烦,故在数据结构的研究中很少提及时间复杂度。为了便于比较同一个问题的不同算法,通常做法是,从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作重复执行的次数做为算法的时间量度。基本操作应是其重复执行次数和算法时间成正比的原操作,多数情况下它是最深层循环内的语句中的操作。算法的执行次数还要随输入集有关,此时要考虑所有可能输入数据的期望值,此时的算法时间复杂度叫平均时间复杂度。有事平均时间复杂度难以确定,此时分析最坏情况下算法的一个上界,此时称为最坏时间复杂度。

2. 时间复杂度的表示方法

  设解决一个问题的规模为n,基本操作被重复执行次数是n的一个函数f(n),则时间复杂度可记作: T(n)=O(f(n)) 它表示随着问题规模n的增长,算法执行时的增长率和f(n)的增长率相同。其中T(n)叫算法的渐进时间复杂度,简称时间复杂度。算法的时间复杂度考虑的只是对于问题规模n的增长率,则在难以精确计算的情况下,只需考虑它关于n的增长率或阶即可。

  例如 

 for(i=2;i<=n;++i)
   
for(j=2;j<=i-1;++j)
   {
    ++x;

    a[i,j]=x;
   }

  其中++x语句频度为:1+2+3+…+n-2=(n-1)(n-2)/2=(n2-3n+2)/2故算法的时间复杂度可表示为:T(n)=O(n2)

3. 时间复杂度的计算方法

  时间复杂的推导方法一般如下:

  第一步:用常数1取代运行时间中的所有加法常数。

  第二步:在修改后的运行次数函数中,只保留最高阶项。

  第三步:如果最高阶项存在且不是1,则去除与这个项相乘的常数。

  时间复杂度一般分为以下几种,分别是:

  (1)常数阶 首先顺序结构的时间复杂度。 

main() 
{
int sum
=0,n=100;
sum
=(1+n)*n/2;
printf(“
%d”,sum);
}

算法的时间复杂度为O(1)。 这个算法的运行次数函数是f(n)=3。根据我们推导的方法,第一步就是把常数项3改为1。在保留最高阶项时发现,它根本没有最高阶项,所以这个算法的时间复杂度为O(1)。

  (2)线性阶 要确定某个算法的阶次,需要确定某个特定语句或某个语句集运行的次数。因此,要分析算法的复杂度,关键就是要分析循环结构的运行情况。 

int i; for(i=0;i<n;i++)
{
/*时间复杂度为O(1)的程序步骤序列*/
}

  (3)对数阶

int count=1;
while(count<n)
{ count
=count*2; /*时间复杂度为O(1)的程序步骤序列*/}

  由于每次count乘以2之后,就距离n更近了一点。也就是说,有多少个2相乘后大于n,则会退出循环。由2x=n得到x=log2n。所以这个循环的时间复杂度为O(log2n)。 
(4)平方阶
inti,j; 
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}
 
循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。间复杂度为O(n2)。

4. 总结

  本文主要讨论算法的时间复杂度,算法时间复杂度在数据结构中是比较难的问题,通过本文给出的计算时间复杂度的方法,能够比较容易掌握时间复杂的计算。