记录学习——算法时间复杂度求法


1.算法时间复杂度的定义:
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)= O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。
用大写O()来体现算法时间复杂度的记法,我们称之为大O记法。
2.推导大O阶方法
  • 用常数1取代运行时间中的所有加法常数。
  • 在修改后的运行次数函数中,只保留最高阶项。
  • 如果最高阶项存在且不是1,则去除与这个项相乘的常数。
  • 得到的最后结果就是大O阶。

常数阶
先举了例子,如下所示。

1 int sum = 0,n = 100; //执行一次  
2 sum = (1+n)*n/2; //执行一次  
3 sum = (1+n)*n/2; //执行二次  
4 sum = (1+n)*n/2; //执行三次  
5 sum = (1+n)*n/2; //执行四次  
6 printf(sum); //执行一次 

上面算法的运行的次数的函数为f(n)=3,根据推导大O阶的规则1,我们需要将常数3改为1,则这个算法的时间复杂度为O(1)。如果sum = (1+n)*n/2这条语句再执行10遍,因为这与问题大小n的值并没有关系,所以这个算法的时间复杂度仍旧是O(1),我们可以称之为常数阶。

线性阶
线性阶主要要分析循环结构的运行情况,如下所示。

1 for(int i=0;i<n;i++){
2 //时间复杂度为O(1)的算法
3 ...
4 }

上面算法循环体中的代码执行了n次,因此时间复杂度为O(n)。

对数阶
接着看如下代码:

1 int number=1;
2 while(number<n){
3 number=number*2;
4 //时间复杂度为O(1)的算法
5 ...
6 }

可以看出上面的代码,随着number每次乘以2后,都会越来越接近n,当number不小于n时就会退出循环。假设循环的次数为X,则由2^x=n得出x=log₂n,因此得出这个算法的时间复杂度为O(logn)。

 

平方阶
下面的代码是循环嵌套:

1  for(int i=0;i<n;i++){   
2       for(int j=0;j<n;i++){
3          //复杂度为O(1)的算法
4          ... 
5       }
6   }

内层循环的时间复杂度在讲到线性阶时就已经得知是O(n),现在经过外层循环n次,那么这段算法的时间复杂度则为O(n²)。

其他常见复杂度

除了常数阶、线性阶、平方阶、对数阶,还有如下时间复杂度:
f(n)=nlogn时,时间复杂度为O(nlogn),可以称为nlogn阶。
f(n)=n³时,时间复杂度为O(n³),可以称为立方阶。
f(n)=2ⁿ时,时间复杂度为O(2ⁿ),可以称为指数阶。
f(n)=n!时,时间复杂度为O(n!),可以称为阶乘阶。
f(n)=(√n时,时间复杂度为O(√n),可以称为平方根阶。

一个进阶实例:

1 int num1, num2;
2 for(int i=0; i<n; i++){ 
3      num1 += 1;
4      for(int j=1; j<=n; j++){ 
5          num2 += num1;
6      }
7 } 

分析:
语句int num1, num2;的频度为1;
语句i=0;的频度为1;
语句i<n; i++; num1+=1; j=1; 的频度为n;
语句j<=n; j++; num2+=num1;的频度为n*n;
T(n) = 2 + 4n + 3n*n

所以时间复杂度是:n^2

 

 


作者:Da4er,发布于:2019/07/12
原文:https://www.cnblogs.com/Da4er/p/11174106.html