JavaScript 算法之最好、最坏时间复杂度分析

上一篇文章中介绍了复杂度的分析，相信小伙伴们对常见代码的时间或者空间复杂度肯定能分析出来了。

思考测试

话不多说，出个题目考考大家，分析下面代码的时间复杂度(ps: 虽然说并不会这么写)

function find(n, x, arr) {
        let ind = -1;
        for (let i = 0; i < n; i++) {
          if (arr[i] === x) ind = i;
        }
        return ind;
      }
复制代码

上面函数的功能就是查找一个变量 x 是否在 数组 arr 中，如果在的话，返回所在的位置，否则就返回 -1。通过上一节的学习分析，这个函数的时间复杂度就很容易知道了，为 O(n)。

接下来，稍微优化下这个 find 函数，如果查找到目标的话，就没必要再往后查找了。

请分析下优化后函数的时间复杂度：

function find(n, x, arr) {
        let ind = -1;
        for (let i = 0; i < n; i++) {
          if (arr[i] === x) ind = i;
          break;
        }
        return ind;
      }
复制代码

现在代码的时间复杂度还为 O(n)吗？不确定，利用上一章的分析法就无法解决了。

不同情况

因为要查找的变量 x 可能会出现在数组的任意位置。如果变量 x 恰好是数组中第一个元素，那么函数就会 break ，后续就不会继续遍历了，那时间复杂度就是 O(1)。但如果恰好是数组中第末个元素，或者数组中不存在变量 x 的话，那就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)。所以，不同的情况下，这个函数的时间复杂度是不一样的。

那为了表示代码在不同情况下的不同时间复杂度，需要了解以下三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度**。
复制代码

理想情况

最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度。比如说刚才那段函数，在最理想的情况下，要查找的变量 x 正好是数组的第一个元素，这种情况下对应的时间复杂度就是 最好情况时间复杂度 。

糟糕情况

最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度。比如说刚才那段函数，要查找的变量 x 正好是数组的第末个元素或者不在数组中存在 ，查找函数就会把数组都遍历一遍，这种情况下对应的时间复杂度就是 最坏情况时间复杂度 。

平均情况

但是， 最好情况时间复杂度 和 最坏情况时间复杂度 对应的都是极端情况下的代码复杂度，发生的概率其实并不大。

为了更好地表示平均情况下的复杂度，引入另一个概念：平均情况时间复杂度，简称为平均时间复杂度。

那如何分析平均时间复杂度呢，还是拿刚才那段查找函数来说：

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

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

但是上面计算的过程中，没有考虑到概率的问题，因为出现在每个位置的概率是不一样的，所以得重新计算，如下分析：

要查找的变量 x，要么在数组里，要么就不在数组里。简单标记这两种情况下的概率都为 1/2。另外，要查找的数据出现在 0～n-1 这 n 个位置的概率也是一样的，为 1/n。所以，根据概率乘法法则，要查找的数据出现在 0～n-1 中任意位置的概率就是 1/(2n)。那我们把每种情况发生的概率都考虑进去，计算表达式就变成了：

最后的结果也叫做概率中的 加权平均值 ，那最后此段函数的 平均时间复杂度 就为 O(n)。

这么看， 平均时间复杂度 是不是好麻烦，还需要概率计算。实际上，在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。很多时候，我们使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。

均摊情况

接下来再看一个概念，特殊的平均时间复杂度：均摊时间复杂度。

先来看一个特殊的函数，分析下它的时间复杂度：

{
      var arr = new Array(n); // n 代表任意数字
      var ind = 0;
      function add(num) {
        if (ind === arr.length) {
          var sum = 0;
          for (var i = 0; i < arr.length; i++) {
            sum += arr[i];
          }
          arr[0] = sum;
          ind = 1;
        }
        arr[ind] = num;
        ind++;
      }
    }
复制代码

add 函数就是实现一个往数组中添加数据的功能。先定义一个任意长度的空数组，然后给数组添加数据。当达到数组长度后，也就是 ind === array.length 时，用 for 循环遍历数组求和，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空的话，则直接将数据添加到数组中。

来分析下此函数的时间复杂度：

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

接下来分析需要计算的 平均时间复杂度 ：

由于数组的长度是 n，根据数据添加的位置的不同，可以分为 n 种情况，每种情况的时间复杂度是 O(1)。除此之外，还有一种特殊的情况，就是在数组没有空闲空间时添加一个数据，这个时候的时间复杂度是 O(n)。而且，这 n+1 种情况发生的概率一样，都是 1/(n+1)。

所以根据大 O 表示法， 平均时间复杂度 就为 O(1)。

其实 add 函数的平均复杂度不需要这么复杂，接下来我们看看 find 函数和 add 函数的区别：

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

所以，针对这样一种特殊场景的复杂度分析，我们并不需要像之前讲平均复杂度分析方法那样，找出所有的输入情况及相应的发生概率，然后再计算加权平均值。

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

那如何使用摊还分析法来分析算法的 均摊时间复杂度 呢？

还是看 add 函数。每一次 O(n) 的添加操作，都会跟着 n-1 次 O(1) 的添加操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。这就是 均摊分析 的大致方法。

一般情况总结为：

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用 均摊时间复杂度分析 的场合，一般 均摊时间复杂度 就等于 最好情况时间复杂度 。

生活举例

看高人如何把复杂度利用到生活中：

今天你准备去老王家拜访下，可惜老王的爱人叫他去打个酱油，她告诉你说她限时 n 分钟给他去买。

那么你想着以他家到楼下小卖部来回最多一分钟，那么 “最好的情况”就是你只用等他一分钟。

那么也有可能遇到突发情况，比如说电梯没电了，或者路上摔了一跤，天知道他去干了什么，用了 n 分钟。没办法，老婆有令，n 分钟限时，那这就是“最坏的情况”。

那“平均时间复杂度” 就是他有可能是第 1,2,3,...,n 中的某个分钟回来，那平均就是 1+2+3+...n/n，把 所有可能出现的情况的时间复杂度 相加除以情况数 。

“均摊时间复杂度”的话就是把花时间多的分给花时间少的，得到一个中间值。假如 n 是 10 分钟，那么 9 分钟分 4 分钟到 1 分钟那，8 分 3 给 2...，那均摊下来就是 5 分钟。