平均时间复杂度

在了解平均复杂度之前，我们先看一下下面的例子，并尝试进行时间复杂度分析：

function find(array: number[], x: number) {
    let pos = -1;
    for (let i = 0; i < array.length; i++) {
        if (array[i] === x) {
            pos = i;
            break;
        }
    }
    return pos;
}

由于我们无法判断 for 循环到底什么时候会 break。有可能数组第一个元素就是要查找的数字 x，这种情况它的时间复杂度为 。也有可能遍历完整个数组，也没有查找到数字 x，这种情况它的时间复杂度为 。也就是说在不同情况下，它的时间复杂度是不一样的。

在这种情况下，我们要分析时间复杂度，则需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

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

所谓最好情况时间复杂度是指在最理想的情况下执行这段代码的时间复杂度。上面的例子，它的最理想情况下就是循环只执行一次就找到了数字 x，此时它的时间复杂度为 。而最坏情况时间复杂度是指在最糟糕的情况下执行这段代码的时间复杂度。上面的例子，它最糟糕的情况就是遍历了这个数组之后，仍然没有找到数字 x，此时它的时间复杂度为 。

平均时间复杂度

最好情况时间复杂度以及最坏时间复杂度都是对应着极端情况下的代码复杂度，发生的概率并不大。为了更好地表示平均情况下的复杂度，需要使用平均情况时间复杂度。

在查找变量 x 在数组中的问题，从大的方面可以分为两种情况，一种是 x 在数组中，另一种情况是 x 不在数组中。而 x 在数组中的情况，又有 种情况（ 表示数组长度），也就是说，一共有 种情况。为了方便理解，我们假设 x 在数组中与不在数组中的概率都为 %22%20aria-hidden%3D%22true%22%3E%0A%3Cg%20transform%3D%22translate(120%2C0)%22%3E%0A%3Crect%20stroke%3D%22none%22%20width%3D%22620%22%20height%3D%2260%22%20x%3D%220%22%20y%3D%22220%22%3E%3C%2Frect%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%2260%22%20y%3D%22676%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-32%22%20x%3D%2260%22%20y%3D%22-687%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=%5Cfrac%7B1%7D2&id=ofNWm)。

当 x 在数组中，那么 x 有可能出现在索引为 0 到 n-1 的位置，x 出现在每个位置的概率为 。结合之前我们假设 x 在数组中与不在数组中的概率都为 ，所以数字 x 出现在索引为 0 ~ n-1 位置的概率实际上为 。由于 x 出现在位置 1 的时候，循环执行一次，它的时间复杂度为 1；而出现在位置 2 的时候，循环执行两次，它的时间复杂度为 2；如此类推，当 x 出现在位置 n 的时候，由于循环了 n 次，它的时间复杂度为 n；当 x 不在数组时，循环了 n 次，所以它的时间复杂度为 n。所以时间复杂度为 ，这个值就是我们所熟知的加权平均值，也叫期望值。去掉系数后，加权平均时间复杂度仍为 。

应用场景

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