时间复杂度计算题

时间复杂度

• 一、常见的时间复杂度
• 二、时间复杂度的计算过程中的忽略原则
• 三、时间复杂度大O记法
• 四、时间复杂度分析
• • 1、加法法则
  • 2、乘法法则
  • 3、除法法则和减法法则
• 四、图形分析

一、常见的时间复杂度

1. 常数阶

这种与问题规模的大小无关（n的多少），执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶。

int sum = 0, n = 100;       /*执行一次*/
sum = (1 + n) * n / 2;      /*执行一次*/
printf("%d",sum);           /*执行一次*/

2. 线性阶

下面这段代码，它的循环的时间复杂度为O(n)， 因为循环体中的代码须要执行n次。

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

3. 对数阶

由于每次count乘以2之后，就距离n更近了一分。 也就是说，有多少个2相乘后大于n，则会退出循环。 由2^x=n 得到x=log2(n)。 所以这个循环的时间复杂度为O(log2(n))。

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

4. 平方阶

这段代码的时间复杂度为O(n^2)。

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

循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。

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

5、对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度

6、对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度

 

二、时间复杂度的计算过程中的忽略原则

• 加法常数项可以忽略
• 除去最高阶项，其它次项可以忽略
• 与最高次项相乘的常数可以忽略

三、时间复杂度大O记法

T(n)=O(f(n))

该公式中的O表示代码的执行总时间T(n)和其执行总次数f(n)成正比。这种表示法，称之为大O记法。大O记法T(n)=O(f(n))，表示随着代码执行的次数增长（减少），算法执行时间的增长率和f(n)的增长率相同，表示的是算法的渐近时间复杂度，简称时间复杂度。
我们通过下面这个例子，来看一下如何使用该公式；
 

int sum = 0; //执行一次
for (int i = 0; i < n; i++) {//执行n次
	b = 2 * i;//执行n次
	for (int j = 0; j < n; j++) {//执行n*n次
		sum += i + j;//执行n*n次
	}
}

分析得出上面代码执行的总次数f(n) = 1 + n + n + nn + nn = 2n²+2n+1 。
因此可以推出时间复杂度T(n) = O(2n²+2n+1 )。当n趋近于无穷大时，T(n)的增长主要与n²有关系，所以我们通常也将上述代码的时间复杂度写为T(n) = O(n²)；

四、时间复杂度分析

时间复杂度的分析有一个基本的法则：四则运算法则

1、加法法则

如果算法的代码是平行增加的，则只需加上所对应的时间复杂度。
接下来通过以下例子来讲解加法法则
下面代码执行的总次数为：f(n) = 1 + n + n；所以时间复杂度为T1(n) = O(2*n + 1)。当n趋近于无穷大时，T1(n) = O(n)；

int sum = 0;//只执行一次
 
for (int i = 0; i < n; i++) {//执行n次
    count++;//执行n次
}

在上述的代码基础上平行增加部分代码，增加后如下所示：
增加前时间复杂度为：T1(n) = O(2n + 1)，增加部分的代码执行次数f(n) = 1 + n + n + n；所以增加的代码时间复杂度T2(n) = O(3n + 1)；因为代码是平行增加的所以增加后的时间复杂度T(n) = T1(n) + T2(n) = O(5*n + 2)。当n趋近于无穷大时，T(n) = O(n)；

int count = 0;//只执行一次
int sum = 0;//只执行一次
 
for (int i = 0; i < n; i++) {//执行n次
	count++;//执行n次
}
for (int j = 0; j < n; j++) {//执行n次
	sum += j;//执行n次
	sum += 2*j;//执行n次
}

2、乘法法则

如果算法的代码增加的是循环内的嵌套或者函数的嵌套，那么就需要乘上相应的时间复杂度。
如果不能理解这句话，别着急，接着往下看，下面的例子会帮助你理解
接下来通过以下例子来讲解乘法法则
在上面已经分析过，下面的代码时间复杂度T1(n) = O(2*n + 1)，也可以写成T1(n) = O(n)；

int sum = 0;//只执行一次
 
for (int i = 0; i < n; i++) {//执行n次
	count++;//执行n次
}

在上述的基础上我们增加部分代码，增加后如下所示；
下面增加了一个内层循环，增加的部分如果单独看，则执行了m次，但是由于是嵌套增加的，所以当外层循坏执行一次，内层循环就会执行m次。所以当外层循环执行n次时，内层循环就会执行n*m次，所以下面代码执行的总次数f(n) = 1 + n + n + nm + nm。由时间复杂度O的定义可计算出下面代码的时间复杂度T(n) = O(2nm + 2n + 1)。当n和m趋近于无穷大时，可以认为n=m，则可以写为T(n) = O(2n² + 2n + 1)。由于n和m趋近于无穷大，所以T(n)的增长主要受n²的增长影响，所以可以写为T(n) = O(n²)
 

int sum = 0;//只执行一次
 
for (int i = 0; i < n; i++) {//执行n次
	count++;//执行n次
	for (int j = 0; j < m; j++) {//执行n*m次
		count++;//执行n*m次
	}
}

3、除法法则和减法法则

减法和除法我相信大家通过上面的讲述可以自己推导出来，我就不多写了。我把主要的思想写在下面，供大家参考

减法法则，如果是去掉算法中平行的代码，就需要减掉相应的时间复杂度。
除法法则，如果是去掉嵌套内的循环或函数，就需要除去相应的时间复杂度。

四、图形分析

对于上述这些常见时间复杂度，它们的执行次数T(n)和问题规模n的关系如下图：