时间复杂度与空间复杂度分析

作为开发人员，我们都希望在完成功能的基础上让代码运行的更快、更省空间，那如何衡量编写的代码是否更有效率，这就需要我们学会如何分析代码时间复杂度和空间复杂度．

什么是复杂度分析

执行时间和占用空间是代码性能的２个评判标准，我们分别用时间复杂度和空间复杂度去描述这２个标准，二者统称复杂度，复杂度描述的是算法执行时间（或占用空间）随数据规模的增长关系．

为什么需要复杂度分析

有人可能想问我代码运行一下不就知道他执行多长时间了吗，为什么还需要复杂度分析，确实你能够通过这种方法评估出代码的执行效率，但是这样会有一些局限性．

1.测试结果太过于依赖测试环境

同一段代码在不同处理器的机器上运行结果是显然不一样的，这时就不知道应该参考哪个测试结果．

2.测试结果受到数据规模的影响很大

两段不同的代码在数据量比较小的时候可能相差甚微，无法真实反映代码的性能问题．

所以我们需要一个不依赖测试环境同时也不需要有具体的测试数据就能粗略的估计代码的执行效率的方法，也就是复杂度分析．

如何进行复杂度分析

大O复杂度表示法

先看一段代码，求1,2,3...n的累加和

int calc(int n) {
  int sum = 0;　　//第一行
  for(int i = 1; i <=n; i++) {
    sum = sum + i;
  }
  return sum;
}

我们来评估一下这段代码的执行时间，假设每行执行的时间一样，为row_time．第1行需要一个row_time的执行时间，第2，3行分别执行了n次，所以需要2n＊row_time的执行时间，所以这段代码加起来总共的执行时间为(2n+1)＊row_time，虽然我们并不知道row_time的具体时间，但我们发现代码的总执行时间T(n)与代码的执行次数ｎ成正比．我们可以用公式来表示

T(n) = O(f(n))

T(n)代表代码的总执行时间，f(n)代表代码的执行次数，O代表T(n)与f(n)成正比．所以上面的例子中，T(n) = O(2n+1)，我们可以看出大O时间复杂度表示代码执行时间随数据规模的变化趋势，我们简称为时间复杂度．

当n很大时，公式中的常量，系数都可以忽略不计，并不会对变化趋势有太大影响，我们只需记下一个最大量级即可，那么刚刚的例子最后就可以记为T(n) = O(n)

那以后的代码如何去分析其时间复杂度呢，我们有以下法则：

1.看代码执行次数最多的一段，比如循环

2.多段代码取最大量级，比如单循环和多重循环，应取多重循环的复杂度

3.嵌套代码复杂度等于嵌套内外代码复杂度的乘积，比如递归和多重循环等

平时我们有一些常用的复杂度级别，比如O(1) (常数阶)、O(logn) (对数阶)、O(n) (线性阶)、O(nlogn) (线性对数阶)、O(n²) (平方阶)

了解了时间复杂度，那么空间复杂度也不难理解了，时间复杂度表示的是算法执行时间随数据规模增长的变化关系，那空间复杂度则表示的是算法存储空间随数据规模增长的变化关系．

总结

复杂度用来分析算法执行效率与数据规模增长的变化关系，越高阶复杂度的的算法执行效率也就越低，上面列举的复杂度级别从低到高分别为O(1)、O(logn)、O(n)、O(nlogn)、O(n²)．