1-1算法复杂度分析 - 图1

1. 为什么要引入复杂度分析？

  1.  许多人都会很困惑，在实际开发过程中，我们可以通过编译器提供的统计功能或者通过性能测试都可以得出代码的性能，为什么还要多此一举，引入复杂度分析呢？关于这个问题，且看下面分析：
  • 性能测试/编译器统计都属于事后统计，即先完成代码开发，后对性能进行评估，而复杂度分析属于事前统计，根据对复杂度的分析，可以得出代码的执行效率。

  • 性能测试/编译器统计受硬件性能/系统的影响较大，结果为特定情况下的结果，并不具有普遍性。

    通过以上两点，已经可以看出复杂度分析的必要性，不过工程实践中，性能测试也同样重要。

    2. 时间复杂度

    2.1概念

    在介绍时间复杂度之前，我们先看一个例子： ```cpp int i = 0; int j = 0;

for (; i < n; ++i) { j += i; }

  1.  上述代码中，1,2行仅会执行一次，4,6行会执行n次，假设我们认为每行执行的时间均为unittime，那么这段代码执行的总时间为（2+2n）*unittime。由此我们可以得出一个结论：一段代码执行的总时间（T）与每行代码执行次数（代数和）成正比。<br />  将上述结论表示为数学公式为：<br />![](https://cdn.nlark.com/yuque/__latex/0b5454fd7d0f29c250d0cd9d8221ff0f.svg#card=math&code=T%28N%29%20%3D%20O%28f%28n%29%29&height=20&width=120)<br /> 其中T(n)表示一段代码执行总时间，f(n)表示一段代码执行总次数，n为数据规模，O表示T（N）与 f(n) 之间的线性关系。<br /> 套用大O表示法，上述代码的执行时间可以表示为![](https://cdn.nlark.com/yuque/__latex/07a35c54a59998443dd41dc6f75f5729.svg#card=math&code=O%282n%2B2%29&height=20&width=73)。实际上，大O表示法不会表示代码执行的准确时间，仅仅用来描述代码时间与数据规模之间的关系，这种就被称为时间复杂度分析，因为代码执行时间随着n的增大而增大，因此也被称为渐进式时间复杂度分析。
  3. <a name="JGFiE"></a>
  4. #### 2.2 时间复杂度规则
  6. - 加法原则：代码的时间复杂度等于量级最大的那段代码的时间复杂度。
  8.       大O表示法表示一种变化趋势。我们通常会省略系数、低阶、常数项，只记录最大量级。在实际分析过程中，我们也只需要关注量级最大的那段代码即可。
  9. ```cpp
  10. int i = 0;
  11. int j = 0;
  12. int sun = 0;
  14. for (; i < n; ++i)
  15. {
  16.     sum += i;
  17. }
  19. for (i = 0; i < n; ++i)
  20. {
  21.     for (j = 0; j < n; ++j)
  22.     {
  23.         sum += j;
  24.     }
  25. }

通过加法原则，我们可以轻而易举分析出时间复杂度为1-1算法复杂度分析 - 图2。

  • 乘法原则：代码的时间复杂度等于本段代码与其嵌套代码的时间复杂度的乘积。 ```cpp int func() { for (int a = 0; a < n; ++a) {

    1.   // ...

    }

    return 0; }

void main() { int sum = 0; for (int j = 0; j < n; ++j) { sum += func(); } }

  1. 通过乘法原则，我们可以轻而易举分析出时间复杂度为![](https://cdn.nlark.com/yuque/__latex/d131620cedf8a696f88e310c3c36b1f8.svg#card=math&code=O%28n%20%5E%202%29&height=23&width=43)。
  2. <a name="m7GOo"></a>
  3. #### 2.3 常见的时间复杂度
  5. - ![](https://cdn.nlark.com/yuque/__latex/5e079a28737d5dd019a3b8f6133ee55e.svg#card=math&code=O%281%29&height=20&width=34)：表示代码执行时间与数据规模无关（注意：并不是只执行了一行代码）
  6. - ![](https://cdn.nlark.com/yuque/__latex/60d4554fc1d20efd2fe270a75f50433e.svg#card=math&code=O%28logn%29&height=20&width=57)：此种时间复杂度分析比较复杂，我们先看一个例子：
  7. ```cpp
  8. int i = 0;
  9. while (i <= n)
  10. {
  11.     i *= 2;
  12. }

假设代码执行h次，那么1-1算法复杂度分析 - 图3，则1-1算法复杂度分析 - 图4，我们可以得出，代码执行次数为1-1算法复杂度分析 - 图5，时间复杂度表示为1-1算法复杂度分析 - 图6，同第4行代码改为i *= 3，那么时间复杂度为1-1算法复杂度分析 - 图7，根据换底公式，我们通常可以将底数省略，表示为1-1算法复杂度分析 - 图8。

  • 1-1算法复杂度分析 - 图9：此种情况我们已经见过很多了，就不做赘述了。
  • 1-1算法复杂度分析 - 图10：根据乘法原则，我们也可以了解到此种复杂度出现的情景。

    3. 空间复杂度

    空间复杂度与时间复杂度同理。简单看一个例子： ```cpp int a = new int[n]; int b[100];

for (int i = 0; i < 100; ++i) { a[i] = b[i]; }

  1. 代码中第一行申请了n个空间，其他位置的空间都为常数，因此我们可以计算出空间复杂度![](https://cdn.nlark.com/yuque/__latex/7ba55e7c64a9405a0b39a1107e90ca94.svg#card=math&code=O%28n%29&height=20&width=36)。
  2. <a name="nQEhs"></a>
  3. ### 4. 进一步分析复杂度
  4. 上述代码中，代码执行的概率都是一样，但在实际情况中并不会这样。例如：在数组中查找某一个值，最好的情况下仅需执行一次即可，最差的情况下需要执行n次。为了表示代码在不同的情况下的时间复杂度，引入了最好时间复杂度，最差时间复杂度，平均时间复杂度这三个概念。<br />下面我们通过一个例子对这三个概念进行解释：
  5. ```cpp
  6. int ncount = 10;
  7. int nindex = 0;
  8. int *arr = new int[ncount];
  9. int *new_array;
  11. void add(int element)
  12. {
  13.     if (nindex >= ncount)
  14.     {
  15.         new_array = new int[2 * ncount];
  17.         for (int i = 0; i < ncount; ++i)
  18.         {
  19.             new_array[i] = array[i];
  20.         }
  22.         array = new_array;
  23.         ncount = 2 * ncount;
  24.     }
  26.     arr[nindex] = element;
  27.     nindex++;
  28. }

  • 最好时间复杂度：代码在各种情况下执行的最短时间。

    1. 显而易见，当数组中有空闲位置时，达到最好时间复杂度，即![](https://cdn.nlark.com/yuque/__latex/5e079a28737d5dd019a3b8f6133ee55e.svg#card=math&code=O%281%29&height=20&width=34)。

  • 最差时间复杂度：代码在各种情况下执行的最长时间。

    1. 显而易见，当数组刚好满了时，需要执行数组的迁移操作，此时复杂度最差，为![](https://cdn.nlark.com/yuque/__latex/7ba55e7c64a9405a0b39a1107e90ca94.svg#card=math&code=O%28n%29&height=20&width=36)。

  • 平均时间复杂度：代码在各种情况下能达到的平均时间。

    经过分析可知，数组不满的概率为1-1算法复杂度分析 - 图11，此时的时间复杂度均为1，数组满的概率为1-1算法复杂度分析 - 图12，此时的时间复杂度为n，那么经过如下计算：
    1-1算法复杂度分析 - 图13
    最终的平均时间复杂度为1-1算法复杂度分析 - 图14。

  • 均摊时间复杂度：均摊时间复杂度是一种特殊的平均时间复杂度，其一般等于最好时间复杂度。

    1. 上述分析可知，时间复杂度为1的次数为n-1，时间复杂度为n的次数为1，那么我们将n均摊给前面的n-1次，就可以得到最终的均摊时间复杂度O(1)。