复杂度分析

什么是复杂度分析

平常写代码的时候可能从来不会去考虑说这段代码的时间复杂度和空间复杂度是多少，最近接触了极客专栏王铮老师的数据结构专栏课才对这方面的知识有了些了解，抱着学知识不怕水深的态度学了几课，感觉受益匪浅下面这些是一些对复杂度理论的一些了解和记录。

复杂度分析的理论基础的建立在数据结构和算法之上的，只有在数据结构和算法的地方复杂度理论才会有用武之地，复杂度分析可以说是整个算法那学习的精髓，掌握了它数据结构算法内容就掌握了一半。算法和数据库结构的目的解决的就是

  • 快
  • 省

的问题，但是当我们设计或者写出一个算法的时候如何来评估什么算法执行效率高或者使用资源更优秀呢？我们传统的做法可能是 监控、统计、计算执行时间，计算所用的内存资源大小，这种方法其实在有边界的范围内是没什么问题的，比如可以确定代码执行的机器的数据和种类，但是如果代码运行的平台和种类无法确定的话前面这些评估方法可能就没有意义了，我们知道同一段代码在不同CPU，环境，硬件下面执行的时间和效率是不一样的。如果才能在这种大环境下有一个平均并且可靠的评估手段呢，复杂度分析就是为这种情况而生的。

大O时间复杂度分析

大O时间复杂度分析也叫渐进时间复杂度(asymptotic time complexity)，表示代码的执行时间随着数据规模增长而变化。

分析

从CPU角度来看，每一行的代码都执行着类似的操作，读数据-运算-写数据，可以假设没行代码的执行时间都是一样的，都为unit_time。

2和3行代码都需要1个unit_time，4和5行都运行了N次所以需要2n unit_time，这样的话这段代码的总执行时间就是(2n+2) unit_time，看出来的所以代码的执行时间T(n)和每行代码的执行次数成n正比。

1
2
3
4
5
6
7
8
int cal(int n) {
  int sum = 0;
  int i = 1;
  for (; i <= n; ++i) {
    sum = sum + i;
  }
  return sum;
}

有了这个规律可以总结成一个公式，大O表示法。

T（n）= O( f(n) )

T(n)所代表的就是代码的执行时间，f(n)代表代码执行次数的总和，公式中的O表示T(n)和f(n)成正比。

如何分析

这里有三种方法可以参考

  1. 只关心执行次数最多的一段代码
  2. 加分法则总的复杂度等于量级最大的那段代码的复杂度
  3. 乘法法则嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

我这里选第一种来分析下，刚刚说的只关心执行次数最多的一段代码那么，代码中的低阶、系数、常量都可以忽略只需要关系最大的一个量级。

2、3行代码都是常量级别的执行时间，和n的大小无关，所以对于复杂度没有影响。这段代码执行次数最多的一段就是4、5它们的执行次数是和n的大小有关的，这二行代码执行了n次，挑出来我们只关心最大量级代码的执行次数，这段代码的时间复杂度是

O（n）

1
2
3
4
5
6
7
8
int cal(int n) {
  int sum = 0;
  int i = 1;
  for (; i <= n; ++i) {
    sum = sum + i;
  }
  return sum;
}

2、3行代码因为是常量级我们也可以给他一个复杂度的分析就是

O（1）

不管代码是一万行还是几十万行都和n无法，都可以算O(1)。

几种常见的复杂度分析

  • 常量阶 O(n)
  • 对数阶 O(logn)
  • 线性阶 O(n)
  • 线性对数阶 O(nlogn)
  • 平方阶 O(n^^)
  • 立方阶 O(n^^^)
  • 指数阶 O(2(n次方))
  • 阶乘阶 O(n!)

空间复杂度

空间复杂度顾名思义就是算法占用资源内存的分析，空间复杂度也叫渐进复杂度分析，表示算法的存储空间与数据规模之间的增长关系。它和时间复杂度是一样的概念，也是忽略那些常量阶的存储只关系最大的一个存储渐变增长。

代码中i申请了存储空间但是它属于常量阶可以忽略掉，只要n在我们分析的范畴，所以这段代码我们只需要取n。空间复杂度为

O(n)

1
2
3
4
5
6
7
8
9
10
11
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]
  }
}

常用的空间复杂度有O(1)、O（n）、O（n^），像是、O（logn）、O（nlogn）、这样的对数复杂度平时都不用到。

总结

复杂度关键还在于多练多分析，熟能生巧。复杂度它只是一个理论知识因为算法与算法之间没有一个标准来判定好与不好，但是我们通过大O表示法可以界定一个算法属于那种，这样当看到一段算法的时候我们就可以知道这段算法是属于哪个量级的复杂度了，一般来说越复杂的算法它所对应的复杂度也就越高。

极客专栏