大O复杂度表示法

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

具体内容略（如果不懂，请参考第一个链接）

时间复杂度并不能完全代表代码的执行时间。大 O 时间复杂度表示法，会忽略掉常数、系数和低阶，并且统计的对象是语句的频度。不同的语句，执行时间也是不同的。时间复杂度只是表示执行时间随数据规模的变化趋势，并不能度量在特定的数据规模下，代码执行时间的多少。如果时间复杂度中原来的系数是 10，我们现在能够通过优化，将系数降为 1，那在时间复杂度没有变化的情况下，执行效率就提高了 10 倍。对于实际的软件开发来说，10 倍效率的提升，显然是一个非常值得的优化。_

时间复杂度分析实用方法

  1. 单段代码看高频：比如循环。
  2. 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
  3. 嵌套代码求乘积：比如递归、多重循环等。
  4. 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)。

为了表示代码在不同情况下的不同时间复杂度，我们需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

最好、最坏情况时间复杂度

示例代码如下：

  1. // n表示数组array的长度
  2. int find(int[] array, int n, int x) {
  3.     int i = 0;
  4.     int pos = -1;
  5.     for (; i < n; ++i) {
  6.         if (array[i] == x) {
  7.             pos = i;
  8.             break;
  9.         }
  10.     }
  11.     return pos;
  12. }
  • 最好情况时间复杂度为 复杂度分析 - 图1
  • 最坏情况时间复杂度为 复杂度分析 - 图2

    平均情况时间复杂度

    最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实并不大。为了更好地表示平均情况下的复杂度，我们需要引入另一个概念：平均情况时间复杂度，后面我简称为平均时间复杂度。

要查找的变量 x 在数组中的位置，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值，即：

image.png

我们知道，时间复杂度的大 O 标记法中，可以省略掉系数、低阶、常量，所以，把上述这个公式简化之后，得到的平均时间复杂度就是 O(n)。

原文中还有实用概率统计方法讨论了一种加权时间复杂度，此处不在记录。

实际上，在大多数情况下，并不需要区分最好、最坏、平均情况时间复杂度三种情况。只有同一块代码在不同的情况下，时间复杂度有量级的差距，才会使用这三种复杂度表示法来区分。

均摊时间复杂度

均摊时间复杂度，听起来跟平均时间复杂度有点儿像。如前所述，大部分情况下，我们并不需要区分最好、最坏、平均三种复杂度。平均复杂度只在某些特殊情况下才会用到，而均摊时间复杂度应用的场景比它更加特殊、更加有限。

下述代码仅供示例（实际不太会这样写）：

// array表示一个长度为n的数组
// 代码中的array.length就等于n
int[] array = new int[n];
int count = 0;

void insert(int val) {
    if (count == array.length) {
        int sum = 0;
        for (int i = 0; i < array.length; ++i) {
            sum = sum + array[i];
        }
        array[0] = sum;
        count = 1;
    }

    array[count] = val;
    ++count;
}

这段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。

那这段代码的时间复杂度是多少呢？

最理想的情况下，数组中有空闲空间，我们只需要将数据插入到数组下标为 count 的位置就可以了，所以最好情况时间复杂度为 **O(1)**。最坏的情况下，数组中没有空闲空间了，我们需要先做一次数组的遍历求和，然后再将数据插入，所以最坏情况时间复杂度为 **O(n)**。

那平均时间复杂度是多少呢？答案是 O(1)。通过概率论的方法来分析，过程如下。

假设数组的长度是 n，根据数据插入的位置的不同，我们可以分为 n 种情况，每种情况的时间复杂度是 O(1)。除此之外，还有一种“额外”的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度是 O(n)。而且，这 n+1 种情况发生的概率一样，都是 1/(n+1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是：

image.png

先来对比一下这个 insert() 的例子和前面那个 find() 的例子，你就会发现这两者有很大差别。

  1. find() 函数在极端情况下，复杂度才为 O(1)。但 insert() 在大部分情况下，时间复杂度都为 O(1)。只有个别情况下，复杂度才比较高，为 O(n)。
  2. 对于 insert() 函数来说，O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个 O(n) 插入之后，紧跟着 n-1 个 O(1) 的插入操作，循环往复。

针对这种特殊的场景，引入了一种更加简单的分析方法：均还**分析法，通过摊还分析得到的时间复杂度我们起了一个名字，叫均摊时间复杂度**。

对于上述代码，每一次 **O(n)** 的插入操作，都会跟着 **n-1** 次 **O(1)** 的插入操作，所以把耗时多的那次操作均摊到接下来的 **n-1** 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 **O(1)**。这就是均摊分析的大致思路。

在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度**。**

空间复杂度分析

类比时间复杂度，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

参考链接

https://time.geekbang.org/column/article/40036
https://time.geekbang.org/column/article/40447