复杂度分析

如何分析、统计算法的执行效率和资源消耗？


什么是时间复杂度？
表示的是一个算法执行效率与数据规模增长的变化趋势，
所以不管常量的执行时间多大，我们都可以忽略掉。因为它本身对增长趋势并没有影响。

什么是空间复杂度？
渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
比如int i = 0; 申请了一个空间存i=变量i， 空间复杂度为O(1)
如如 int[] a = new int[n];申请了n个空间存储int类型，空间复杂度就是O(n)
比如 int[] a = new int[n][n];二维数组空间复杂度就是O(n^2)


你可能会有些疑惑，我把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。
为什么还要做时间、空间复杂度分析呢？这种分析方法能比我实实在在跑一遍得到的数据更准确吗？
首先，我可以肯定地说，你这种评估算法执行效率的方法是正确的。
很多数据结构和算法书籍还给这种方法起了一个名字，叫事后统计法。但是，这种统计方法有非常大的局限性。
1. 测试结果非常依赖测试环境
2. 测试结果受数据规模的影响很大
后面我们会讲排序算法，我们先拿它举个例子。
对同一个排序算法，待排序数据的有序度不一样，排序的执行时间就会有很大的差别。
极端情况下，如果数据已经是有序的，那排序算法不需要做任何操作，执行时间就会非常短。
除此之外，如果测试数据规模太小，测试结果可能无法真实地反应算法的性能。
比如，对于小规模的数据排序，插入排序可能反倒会比快速排序要快


所以，我们需要一个不用具体的测试数据来测试，就可以 粗略地估计 算法的执行效率的方法。
这就是我们今天要讲的时间、空间复杂度分析方法。


大 O 复杂度表示法：
算法的执行效率，粗略地讲，就是算法代码执行的时间。
但是，如何在不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？

 int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }
  时间复杂度：其实就是求代码的总执行时间T(n)
  每一行代码在cpu看来，都执行类似的操作，读数据-运算-写数据。
  尽管每行代码对应的的cpu执行的个数、执行的时间不一样。
  但是这里我们粗略估算，可以假设每行代码执行的时间都一样，为一个单位时间unit_time。
  那我们求时间复杂度，也就是求代码的总执行时间，只需要把所有代码执行的时间相加就可以了。
  如上代码中 两行赋值的代码都执行一次，记作2*unit_time，循环语句两行代码，一共是2n*unit_time,
  那么总执行时间T(n)=(2n+2)*unit_time
  2n中的2是代码行数，n是代码执行次数，所以，所有代码的执行时间T(n)与每行代码的执行次数成正比。
  如果是双重循环，就是整段代码总的执行时间 T(n) = (2n^2+2n+3)*unit_time
  得出结论：：：：所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。
  我们把这个规律总结成一个公式：T(n) = O(f(n))
  T(n)：代码的总执行时间，n表示数据规模的大小；
  f(n)：每行代码执行的次数总和，n表示表示每行代码的执行次数，因为我们上面的规律得出。
  O：表示代码的执行时间T(n) 和f(n)表达式成正比。

  所以，第一个例子中的 T(n) = O(2n+2)，第二个例子中的 T(n) = O(2n^2+2n+3)。
  这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间，
  而是表示代码执行时间随数据规模增长的变化趋势，
  所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

  当 n 很大时，你可以把它想象成 10000、100000。
  而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。
  我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，
  就可以记为：T(n) = O(n)； T(n) = O(n2)。


  分析时间复杂度的方法：
  1.只关注循环执行次数最多的一段代码
  就是去掉常量、低阶、系数，只记录一个最大阶的量级即可。
  T(n) = O(2n^2+2n+3)：T(n) = O(n^2)
  2.加法法则：   总的时间复杂度就等于量级最大的那段代码的时间复杂度
   如果一段代码有多段循环  每段的时间复杂度分别为O(n) 和 O(n^2)，那我们就取量级最大的作为整段代码的
   时间复杂度，也就是 O(n^2)
   公式：如果 T1(n)=O(f(n))，T2(n)=O(g(n))；
   那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).
   3.乘法法则：  嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
   可以看成嵌套循环，外层的复杂度*内层的复杂度即可


   常见的复杂度量级：
   多项式量级：
   常量阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)
   非多项式量级：
   指数阶O(2^n)、阶乘阶O(n!)   这种当数据规模n越来越大时，执行时间会急剧增加，时间会无限增长。非常低效。


复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系，
可以粗略地表示，越高阶复杂度的算法，执行效率越低。常见的复杂度并不多，
从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )。
等你学完整个专栏之后，你就会发现几乎所有的数据结构和算法的复杂度都跑不出这几个。