干货|算法复杂度分析看这一篇就够了

导读概述

互联网行业中数据结构和算法尤为重要,互联网软件特点：高并发、高性能、高扩展、高可用、海量数据,对编程的追求，了解数据结构和算法能让我们的代码精益求精。
那如何评价算法的好坏呢，有2个重要的指标:时间复杂度和空间复杂度，时间维度是指算法运行结束消耗的时间，空间维度则是执行算法所需占用的内存空间。

本文将从以下几个方面分享给大家：
1.什么是时间复杂度
2.时间复杂度计算规则
3.时间复杂度案例分析
4.什么是空间复杂度
5.空间复杂度计算规则
6.空间复杂度案例分析

时间复杂度

如何计算一个算法的时间复杂度呢

通常采用大O表示法来表示
用 T(n) = O(f(n)) 表示

大 O 时间复杂度表示法,实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫渐进时间复杂度，简称时间复杂度（asymptotic time complexity）。

常见的时间复杂度大O表示法

1.O(1):常量级

// 大O表示法
int a=1;
int b=2;
int count=a+b;

这种是最简单的，也是最好理解的，就是常量级
不是只执行了一行代码，只要代码的执行不随着数据规模(n)的增加而增加，就是常量级
在实际应用中，通常使用冗余字段存储来将O(n)变成O(1)。

2.线性阶：O(n)

// 大O表示法
 int sum(int n){
 int count = 0 ;//t 一个时间单位
 for(int i=0;i<n;i++){//t*n
            count=count+i;//t*n
        }
 return count;
    }

上面的例子中时间复杂度T(n)=O(2n+1),当n无限大时，低阶、常量、系统都可以忽略
即上例中的时间复杂度为T(n)=O(n)，也就是代码执行时间随着数据规模的增加而增长.

3.线性阶O(m+n)

// 大O表示法
 int sum(int m,int n){
 int sum1 = 0 ;
 int sum2 = 0 ;
 for(int i=0;i<=m;i++){// O(m)
        sum1+=i;
    }
 for(int j=1;j<=n;j++){ //O(n)
        sum2+=j; 
    }
 return sum1+sum2;
}

m和n是代码的两个数据规模，而且不能确定谁更大，此时代码的复杂度为两段时间复杂度之和,即 T(n)=O(m+n)
记作：O(m+n)

**4.O(m*n)**

// 大O表示法
 int sum(int m,int n){
 int sum = 0 ;
 for(int i=0;i<=m;i++){// m
 for(int j=1;j<=n;j++){ //m*n
            sum=i+j; //m*n
        }
    }
 return sum;
  }
}

根据乘法法则代码的复杂度为两段时间复杂度之积，即
T(n)=O(m*n)
记作：O(m*n)
当m==n时,为O(n*n)

**5.平方阶 O(n*n)**

// 大O表示法
 int sum(int n){
 int count = 0 ;//t 一个时间单位
 for(int i=0;i<n;i++){//n
 for(int j=0;j<n;j++){//n*n 
        count=count+i+j;
      } 
    }
 return count;
}

上例为：T(n)=O(n*n)
也就是代码执行时间随着数据规模的增加而平方增长
依此类推，时间复杂度也成为渐进增长：
两次嵌套for时间复杂度：O(n^2)
三层嵌套for时间复杂度：O(n^3)
k层嵌套for时间复杂度:O(n^k)

6.O(n^2)

// 大O表示法
 int count = 0 ;//t 一个时间单位
 for(int i=0;i<n;i++){
 //O(n)
    }
 for(int i=0;i<n;i++){//n
 for(int j=0;j<n;j++){//n*n
            count=count+i+j;
        }
    }

时间复杂度： T(n)=O()+O(n)
简写：T(n)=O()
注：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积(乘法法则)

7.对数阶 O(logn)

// 大O表示法
int i=1；
while(i<n)
{
      i=i*2;
}

O(logn)推导过程:
以上代码，while循环中每次将i乘以2，直到i大于n，结束此循环。
如循环n次后，i>n，循环结束，也就是2的i次方等于n即i=log2n，也就是说循环log2n次以后，代码就结束了。代码的时间复杂度为O(logn)。
找出while循环中的结束条件，判断时间复杂度。带有while循环的代码，大概率是对数时间复杂度为
T(n)=O(n*logn)即O(logn)

小结：

常用的时间复杂度所耗费的时间从小到大依次是：
O(1) < O(logn) <O (n) < O(nlogn) < O() < O() < O() < O(n!) < O(nn)

空间复杂度

例如将一个数组拷贝到另一个数组中，就是相当于空间扩大了一倍:
记作：T(n)=O(2n)，忽略系数。即为O(n)

常见的空间复杂度

空间复杂度比较常用的有：O(1)、O(n)、O(n²)

1.O(1)空间复杂度

// 大O表示法
int i = 1;
int j = 2;
int count = i + j;

以下i，j和count变量所分配的临时空间不随处理数据量的变化而变化，因此它空间复杂度为O(1)

2.O(n)空间复杂度

// 大O表示法
 void method(int n) {
 int[] array = new int[n];//O(n)
 for (int i = 1; i <= array.length; ++i) {
 //业务代码
    }
  }

上述代码中的第一行代码new了一个数组，数组中有n个数据，剩余代码中虽然有循环，但是没有再分配新的空间，因此，该代码段的空间复杂度主要体现在第一行，为O(n)。平方阶的空间复杂度与之类似，依此类推即可。
常见的空间复杂度就是O(1)、O(n)、O()，而O(logn)、O(nlogn)空间复杂度平时用的少些。

后记

本文对算法中的时间复杂度和空间复杂度进行了简单的分析和介绍,希望对大家有所帮助,如果感觉有所收获，可以动动小手指给点个赞，感谢阅读!

发布于 2021-11-25 23:42

算法分析

算法

算法工程师