算法时间复杂度分析(二)

之前讲过了关于时间复杂度的具体内容,这篇文章主要写以下内容:

  • 最好情况时间复杂度(best case time complexity)
  • 最坏情况时间复杂度(worst case time complexity)
  • 平均情况时间复杂度(average case time complexity)
  • 均摊时间复杂度(amortized time complexity)

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

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;
}

代码功能是在无序数组中找到指定元素 x 出现的位置。按照之前的分析方法,这段代码的复杂度为 O(n),其中 n 代表数组的长度。

在数组中查找一个数据,不是都需要把整个数据都遍历一遍,可能在半途就找到,那这时候就可以提前结束循环。由此可见,上面的代码不够高效,下面是进行优化的代码。

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 可能出现在数组的任意位置,如果数组的第一个元素就是变量 x,那就不需要遍历剩下的 n - 1 个元素了,这时的时间复杂度为 O(1)。如果变量 x 就不存在数组中,就需要把整个数组遍历一遍,时间复杂度就变成了 O(n)。所以,这段代码在不同情况下,它的时间复杂度是不一样的。

于是,就有了三个概念:最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。最好和最坏情况时间复杂度在上面的解释中,很好理解。

平均情况时间复杂度

最好和最坏对应的都是极端情况下的代码复杂度,发生的概率并不大。对于上面的代码,在查找变量 x 在数组中的位置时有 n + 1 种情况:在数组 0 ~ n-1 位置中和不在数组中。把每种情况查找需要遍历的元素个数累加起来,再除以 n + 1,就能得到需要遍历的元素个数的平均值:

$$\frac{1 + 2 + 3 + … + n + n}{n + 1} = \frac{n(n + 3)}{2(n + 1)}$$

时间复杂度的大 O 标记法中,可以省略系数、低阶、常量,把上面的公式简化后,得到的平均情况时间复杂度为 O(n)。

这个结论虽然正确,但是这里的 n + 1 种情况出现的概率并不一样,在查找时,要么在要么不在,假设它们的概率都为 1/2,数据出现在数组中的概率也都为 1/n。这时要查找数据出现在数组中任意位置的概率为 1/(2n)。

上面推导中存在最大的问题就是没有把各种情况发生的概率考虑进去,如果考虑后,平均情况时间复杂度计算如下:

$$1 \times \frac{1}{2n} + 2 \times \frac{1}{2n} + … + n \times \frac{1}{2n} + n \times \frac{1}{2n} = \frac{3n + 1}{4}$$

这个值在概率论中叫做 加权平均值(期望值),所以平均情况时间复杂度的全称应该叫做 加权平均情况时间复杂度 或者 期望时间复杂度

所以代码的加权平均值为 (3n+ 1)/4,用大 O 表示法应去掉系数和常量,最终该代码的加权平均时间复杂度仍然是 O(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;
}

这段代码实现了往数组中插入数据,且当数组满了之后进行遍历求和并清空数组,再将求和后的 sum 值放到数组的第一个位置,然后再将新的数据插入,但如果数组一开始就有空间,则直接插入。

最理想情况下,有空位置,把数据插入到数组下标为 count 的位置即可,复杂度为 O(1)。最坏情况下,没有空位置,先遍历求和再插入,复杂度为 O(n)。

假设数组长度为 n,根据插入位置的不同,可以分为 n 种情况,每种情况复杂度为 O(1)。除此外还有一种情况,就是没有位置的时候,这时复杂度为 O(n),并且 n + 1 中情况发生的概率一样,都是 1/(n + 1),所以得到的平均情况时间复杂度为:

$$1 \times \frac{1}{n + 1} + 1 \times \frac{1}{n + 1} + … + n \times \frac{1}{n + 1} = O(1)$$

这里代码并不需要引入概率论的知识,每种情况出现的频率是非常有规律的,并且有一定的前后时序关系,一般都是一个 O(n) 插入后,紧跟着 n - 1 个 O(1) 的插入操作,循环往复。

针对这样一种特殊场景的复杂度分析,不需要像前面平均情况时间复杂度分析方法一样先找出输入情况及相应的发生概率,然后再计算加权平均值。

于是便引入了另外一种分析方法:摊还分析法,通过此方法得到的时间复杂度叫做 均摊时间复杂度

在插入数据的代码中,每一次 O(n) 插入操作后都有 n - 1 次 O(1) 的插入操作,把耗时多的那次操作均摊到接下来的 n - 1 次耗时少的操作上,这一组连续操作的均摊时间复杂度就是 O(1),这就是均摊分析的大致思路。

均摊应用场景比较特殊,并不会经常用到,在能够应用均摊的场合,一般均摊等同于最好。

如果觉得这篇文章不错,不妨

微信打赏 微信打赏
支付宝打赏 支付宝打赏
Nginx 禁止未绑定域名访问
Git 使用 —— 本地环境使用