领取淘宝天猫优惠券:优惠淘 | 欢迎使用随心而码微信小程序,微信搜一搜【随心而码】可直接搜到。

常用数据结构与算法时间复杂度求解

数据结构 Hicoder 1239℃ 0评论

1.0 数据结构的相关概念

2.0 一些基本算法的时间复杂度

O(1):

 
int x=1;

O(n):

 
 for(int i = 0; i < n; i++){
   printf("%d",i);
 }

O(log2n):

 
 int n = 8,count = 0;
 for(int i = 1; i <= n; i*=2){
   count++;
 }

O(n2):

 
 int n = 8,count = 0;
 for(int i = 1; i <= n; i++){
   for(int j = 1; j <= n; j++){
     count++;
   }
 }

O(nlog2n):

 
 int n = 8,count = 0;
 for(int i = 1; i <= n; i*=2){
   for(int j = 1; j <= n; j++){
     count++;
   }
 }

2.1 求解时间复杂度的基本步骤

(1)找出算法中的基本语句:算法中执行次数最多的,通常是内层循环的循环体;

(2)计算基本语句的执行次数的数量级;

(3)用大O记号表示算法的时间性能,将基本语句执行次数的数量级放入大O记号中。

2.1.0 例题解析

eg1:

 
 #include <stdio.h>

 int main(){
   int i, j, x = 0, sum = 0, n = 100; //执行了1次
   for( i = 1; i <= n; i++){ //执行了n+1次
     sum = sum +i; //执行了n次
     for(j = 1; j <= n; j++){ //执行了n*(n+1)次
       x++; //执行了n*n次
       sum =sum + x; //执行了n*n次
     }
   }
   printf("%d",sum); //执行了1次
 }

很显然,一共执行了 1+(n+1)+n+n(n+1)+ n n +n*n =3n2 +3n +2次,去掉常数,保留最高阶,化最高阶系数为1,得到数量级O(n2)。即时间复杂度为:T(n)=O(n2)。

eg2:计算 1+2+3+4+······+100

 
 #include <stdio.h>

 int main(){
   int i , sum = 0,n = 100; //执行了1次
   for(i = 1; i <= n; i++){ //执行了n+1次
     sum +=i; //执行了n次
   }
   printf("%d",sum); //执行了1次
 }

显然的,算法所用时间(语句执行频度)为:1+n+1+n+1 = 2n+3次,故时间复杂度为:O(n)。

eg3:计算 1+2+3+4+······+100 (高斯算法)

 
 #include <stdio.h>

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

时间复杂度为:O(3),记为O(1)。

eg4: 求两个n阶方阵C=A * B的乘积,算法如下

 
 void MatrixMultiply(int A[n][n], int B[n][n], int C[n][n]){
   for(int i = 0; i < n; i++){ //执行了n+1次
     for(j = 0; j < n; j++){ //执行了n*(n+1)次
       C[i][j] = 0; //执行了n^2^次
       for(k = 0; k < n; k++){ //执行了n^2^*(n+1)次
         C[i][j] = C[i][j] + A[i][k] *B[k][j]; //执行了n^3^次
       }
     }
   }
 }

则T(n)=2n3+3n2+2n+1,故时间复杂度为O(n3)。

eg5:

 
 void test(int n){
   i = 1,k = 100;
   while(i < n){
     k = k+1;
     i = i+2;
   }
 }

求解步骤:

 
 假设循环体执行了T(n)次,
 当循环体(i=i+2)执行了1次时,i = 1 + 2;
 当循环体(i=i+2)执行了2次时,i = 2 + 2;

以此类推,很显然,i =2T(n) +1,又循环条件为 i < n,
即 2T(n) +1 <= n-1,解得T(n) <= n/2 -1,故时间复杂度为O(n)。

2.1.1 常见时间复杂及其效率高低比较(由高到低)

O(1) > O(logn) > O(n) > O(nlogn) > O(n2) > O(n3) > O(2n) > O(n!) > O(nn)。如果你设计的算法时间复杂度为O(2n)以后的,那么你必须修改你的算法了。很显然,常数阶(O(1))效率最高,比如高斯算法。

3.0 总结

数据结构与算法是计算机专业必修课程,也是计算机专业考研的重点,必须学好。紫罗兰

转载请注明:随心而码 » 常用数据结构与算法时间复杂度求解

喜欢 (5)