复杂度分析（下）

+文本内容是对王争《数据结构与算法之美》课程的笔记，如果有任何侵权行为，请联系博主删除

最好、最坏时间复杂度

先给个例子:

// n 表示数组 array 的长度
int find(int[] array, int n, int x){
    int i = 0;
    int pos = -1;
    for(; i<n; ++i){
        if (array[i] == x){
            pos = i;
        }
    }
    return pos
}

按照上次的分析方法, 这段代码的复杂度是 $O(n)$ , 其中, n代表数组的长度.

但是在数组中查找一个数据, 不需要从头到尾遍历一遍, 在中间可能就可以提前结束循环. 优化代码.

// n 表示数组 array 的长度
int find(int[] array, int n, int x){
    int i = 0;
    int pos = -1;
    for(; i<n; ++i){
        if(array[i] == x){
            pos = i;
            break;
        }
    }
    return pos;
}

如果数组的第一个元素正好是要查找的变量 $x$ , 那时间复杂度是 $O(1)$ . 但是如果数组中不存在变量 $x$ , 那时间复杂度是 $O(n)$ .

由此引入三个概念: 最好情况时间复杂度、最坏情况时间复杂度和平均情况复杂度.

最好情况时间复杂度和最坏情况时间复杂度都很好理解, 重点记录一下平均情况时间复杂度.

平均情况时间复杂度

查找变量x在数组中的位置, 有n+1种情况: 在数组的 $0 \sim n-1$ 位置中和不在数组中. 把每种情况下, 需要遍历的元素累加起来, 然后再除以n+1, 就可以得到需要遍历的元素个数的平均值, 即:
$\frac{1+2+3+\cdots+n-1+n}{n+1} = \frac{n(n+3)}{2(n+1)}$
将其简化后可得 $O(n)$ . 但是, 这个结果是有问题的, 因为每种情况出现的概率不一样.

要查找的变量 $x$ , 要么在数组里, 要么不在数组里. 为了方便理解, 假设在数组中与不在数组中的概率都为 $\frac{1}{2}$ . 另外, 要查找的数据出现在 $0 \sim n-1$ 这 $n$ 个位置的概率也是一样的, 为 $\frac{1}{n}$ . 所以, 根据概率乘法法则, 要查找的数据出现在 $0 \sim n-1$ 中任意位置的概率就是 $\frac{1}{2n}$ .

计算过程为:
$1 \times \frac{1}{2n}+2 \times \frac{1}{2n}+3\times\frac{1}{2n}+ \cdots +n \times \frac{1}{2n} + n \times \frac{1}{2} = \frac{3n+1}{4}$
这个值就是概率论中的加权平均值, 也叫作期望值, 所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度.

这段代码的加权平均时间复杂度仍然是 $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$ 的位置就可以了, 所以最好情况时间复杂度为 $O(1)$ . 最坏的情况下, 数组中没有空闲空间了, 我们需要先做一次数组的遍历求和, 然后再将数据插入, 所以最坏情况时间复杂度为 $O(n)$ .

而平均时间复杂度是 $O(1)$ . 我们还是可以通过概率论的方法来分析.

假设数组的长度是n, 根据数据插入的位置的不同, 我们可以分为n种情况, 每种情况的时间复杂度是O(1). 除此之外, 还有一种"额外"的情况, 就是在数组没有空闲空间时插入一个数据, 这个时候的时间复杂度是O(n). 而且, 这n+1种情况发生的概率一样, 都是\frac{1}{n+1}. 所以, 根据加权平均的计算方法, 我们求得的平均时间复杂度就是:
$1 \times \frac{1}{n+1}+1\times\frac{1}{n+1}+\cdots+1\times\frac{1}{n+1}+n\times\frac{1}{n+1} = O(1)$
其实这个例子不需要引入概率论的知识, 对比一下 $insert()$ 和 $find()$ 的例子, 就会发现这两者有很大的差别.

首先, $find()$ 在极端情况下, 复杂度才为 $O(1)$ . 但 $insert()$ 在大部分情况下, 时间复杂度都为 $O(1)$ . 只有个别情况下, 复杂度才为 $O(n)$ . 这是 $insert()$ 第一个区别与 $find()$ 的地方.

第二个不同点, 对于 $insert()$ 函数来说, $O(1)$ 时间复杂度的插入和 $O(n)$ 时间复杂度的插入, 出现的频率是非常有规律的, 而且有一定的前后时序关系, 一般都是一个 $O(n)$ 插入之后, 紧跟着 $n-1$ 个 $O(1)$ 的插入操作, 循环往复.

针对这样一种特殊场景的复杂度分析, 我们并不需要像之前那样, 找出所有的输入情况及相应的发生概率, 然后计算加权平均值. 为此, 引入一种更加简洁的分析方法: 摊还分析法, 通过摊还分析法得到的时间复杂度我们起了一个名字, 叫均摊时间复杂度.

针对上述例子, 每一次 $O(n)$ 的插入操作, 都会跟着 $n-1$ 次 $O(1)$ 的插入操作, 所以把耗时多的那次操作均摊到接下来的 $n-1$ 次耗时少的操作上, 均摊下来, 这一组连续的操作的均摊时间复杂度就是 $O(1)$ .

总结其应用场景:

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