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

什么是复杂度剖析

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

为什么需要复杂度剖析

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

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²)．

来自：https://segmentfault.com/a/1190000018129300

链接: http://www.fly63.com/article/detial/1985