数据结构与算法二：复杂度分析（上）

文章目录

复杂度分析的必要性
大O复杂度表示法(时间复杂度)
几种常见的时间复杂度分析
空间复杂度分析
总结

复杂度分析的必要性

通过跑代码得到算法执行的时间和占用空间局限性非常大，其测试结果非常依赖测试环境，测试结果也受数据规模的影响很大，所以我们需要一个不用具体的测试数据来测试，就可以粗略的估计算法的执行效率的方法。

大O复杂度表示法(时间复杂度)

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

时间复杂度可以由以下三个比较实用的方法来分析

只关注循环执行次数最多的一段代码

我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环次数最多的那段代码就可以了
```
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
 sum = sum + i;
}
return sum;
}
```
当n很大时，可以想象成10000，1000000。而代码中的低阶、常量、系数三个部分并不左右增长趋势，所以可以忽略。我们只需要记录一个最大量级就可以了。

第二三行都是常量级的执行时间，与n的大小无关，所以对于时间复杂度没有影响。执行时间最多的是第四五行代码，都被执行了n次，所以时间复杂度为O(n)
加法法则，总复杂度等于量级最大的那段代码的复杂度
```
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
 sum_1 = sum_1 + p;
}

int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
 sum_2 = sum_2 + q;
}

int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
 j = 1; 
 for (; j <= n; ++j) {
   sum_3 = sum_3 +  i * j;
 }
}

return sum_1 + sum_2 + sum_3;
}
```
这段代码分为三个部分，sum_1、sum_2、sum_3，我们可以分析每一部分的时间复杂度，然后把它们放到一块儿，再取一个量级最大的作为整段代码的时间复杂度。

第一部分执行了100次，所以是一个常量的执行时间，与n的规模无关，所以这里的时间复杂度记为O(1)

第二部分时间复杂度 O(n)，第三部分时间复杂度 O(n²)。综合三段代码，取其中最大的量级，所以这段代码的时间复杂度为O(n²)
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
```
int cal(int n) {
int ret = 0; 
int i = 1;
for (; i < n; ++i) {
 ret = ret + f(i);
} 
} 

int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; ++i) {
sum = sum + i;
} 
return sum;
}
```
单看cal函数，时间复杂度为O(n)。但f函数不是一个简单的操作，f函数的时间复杂度可以看出为O(n)，所以，整个cal函数内的时间复杂度为两个复杂度的成绩O(n²)

几种常见的时间复杂度分析

以下几种复杂度量级几乎涵盖了所有代码的复杂度量级

以上罗列的复杂度量级，我们可以粗略的分为两类，多项式量级和非多项式量级。非多项式量级只有两个：O(2ⁿ)、O(n!)

当n越来越大时，非多项式量级算法的执行时间会急剧增加，执行时间会无限增长，所以非多项式时间复杂度的算法其实是非常抵消的。因此我们主要来看几种多项式时间复杂度

O(1)
首先要明确一个概念，O(1)这是常量级时间复杂度的一种表示方式，并不是指只执行了一段代码
```
int i = 8;
int j = 6;
int sum = i + j;
```
一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行代码，时间复杂度也是O(1)
O(logn)、O(nlogn)
```
i=1;
while (i <= n)  {
i = i * 2;
}
```
从代码中看出，i从1开始取，每循环一次乘以2，由此得出：

所以，我们只需要知道x是多少，就能知道这段代码的执行次数了。通过2^x=n可以得出，x=log(2)n，所以这段代码的时间复杂度为log(2)n。

我们知道，对数之间是可以互相转换的 log(3)n = log(3)2 log(2)n，所以O(log(3)n) = O(log(3)2 log(2)n)，其中Log(3)2是常量，可以忽略系数，所以log(3)n = log(2)n。

在对数的时间复杂度的表示法里，我们忽略对数的底，统一表示为O(logn)。所以这段代码的最终时间复杂度为O(logn)

利用乘法法则，我们可以很轻易的了解到O(nlogn)，即如果一段时间复杂度为O(logn)的代码执行了n次，时间复杂度就为O(nlogn)了。O(nlogn)是一种非常常见的时间复杂度，比如，归并排序、快速排序。
O(m+n)、O(m*n)
```
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}

int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}

return sum_1 + sum_2;
}
```
这段代码分为两个部分，第一部分的时间复杂度为O(m)，第二部分的时间复杂度为O(n)。但我们无法评估m和n谁的量级大，所以我们在表示时间复杂度的时候，就不能简单的利用加法法则省略掉其中一个。所以，这段代码的时间复杂度为O(m+n)。

这种情况的加法法则就不正确了，时间复杂度改为了m+n，但乘法法则依然有效。

空间复杂度分析

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i <n; ++i) {
    a[i] = i * i;
  }

  for (i = n-1; i >= 0; --i) {
    print out a[i]
  }
}

从第二行代码可以看出，我们申请了一个空间存储变量i，但它是常量阶的，跟数据规模n无关，所以我们可以忽略。第三行申请了一个大小为n的int类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度为O(n)。

我们常见的空间复杂度有O(1)、O(n)、O(n²)，像 O(logn)、O(nlogn)这样的对数阶复杂度平时都用不到

总结

复杂度也叫渐进复杂度，包括时间和空间，用来分析算法执行效率与数据规模之间的增长关系，可以粗略的表示，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)

文章目录

复杂度分析的必要性

大O复杂度表示法(时间复杂度)

几种常见的时间复杂度分析

空间复杂度分析

总结

书签