算法算法分析

可清空表的摊销分析

字数统计: 1.4k字   |   阅读时长: 4分
, ,

摘要: 摊销分析的例子

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，前面几篇文章我们讨论了一些数据结构。根据实际需求设计的一个数据结构，往往支持很多操作。当我们谈这个数据结构的效率怎么样的时候，通常我们会分析每个操作在最坏情况下的时间复杂度。

那么一种常见的情况是各个不同的操作，时间复杂度差别很大。数据结构在实际应用中的效率到底怎么样，往往就取决于实际的操作序列中各个操作的分布情况。如果时间复杂度高的操作多，那么体感上就是效率不太好；如果时间复杂度低的操作多，那么虽然某些操作效率很低，但是实际体感上好像并不明显。

基于以上直觉，我们就有了讨论摊销分析的动机，即给定一个长度为 $n$ 的操作序列，在最坏的情况下，这个操作序列整体的时间复杂度是多少。再除以 $n$ 就是摊销到每个操作上的时间复杂度。

摊销分析与常规的基于每个操作的最坏情况运行时间的算法分析相比，主要的区别在于，它不是单独分析每一个操作，而是通过研究这些操作序列的运行时间，来考虑所有操作之间的相互作用。

本文我们通过一个简单的例子来初步了解一下摊销分析。

可清空表

考虑一个在数组上维护的线性表，其中元素可用通过下标访问。在这样的线性表上，我们实现一个可清空表，支持以下两个操作：

  • add(x)，将元素 x 添加到表的末尾。
  • clear()，移除所有的元素，使其变成空表。

设 $S$ 为一个具有 $n$ 个元素的可清空表，则按照常规的算法分析的观点，在最坏的情况下，add(x) 的时间复杂度为 $\Theta(1)$，clear() 操作需要 $\Theta(n)$ 的时间复杂度。

那么对于一个长度为 $n$ 的操作序列，非常直接的观点就是认为最坏情况是 $n$ 个操作全是 clear() 操作，而一次 clear() 操作最坏情况的时间复杂度为 $\Theta(n)$，于是整体的最坏情况的时间复杂度为 $\Theta(n^{2})$。

但这个观点明显错误，因为如果真的所有操作全是 clear()，那么每次 clear() 的时间复杂度都是 $O(1)$，如果有多次 clear()，也不是每次 clear() 时表里都有 $O(n)$ 个元素。

所以长为 $n$ 的操作序列，考虑操作之间的相互影响，整体的时间复杂度要比 $O(n^{2})$ 要低，但具体是多少，就需要摊销分析。

摊销分析

定理

假设一个可清空表 $S$ 用数组实现，那么在空的可清空表上的 n 个操作需要 $O(n)$ 的时间复杂度。

证明

令 $M_{0}, \cdots, M_{n-1}$ 表示 $S$ 上进行的 $n$ 个操作的序列，令 $M_{i_{0}}, \cdots, M_{i_{k-1}}$ 表示其中 $k$ 个 clear 操作。则有：

令 $i_{-1} = -1$，则 $M_{i_{j}}$ 操作的运行时间为 $O(i_{j} - i_{j-1})$，因为在上一次 clear 操作 $M_{i_{j-1}}$（第 $i_{j-1}$ 个操作）之后，或者从开始状态之后，最多有 $i_{j} - i_{j-1}$ 个元素添加到表中（add 操作），而一次 add 的时间复杂度是 $O(1)$，因此 k 次 clear 操作的总运行时间为：

以上和式也称为伸缩和，除第一项和最后一项，其它项都相互抵消了，因此上述和式的结果为 $O(i_{k-1} - i_{-1})$，即 $O(n)$。

另一方面，操作序列中的其它所有操作，也就是 add，一次的运行时间为 $O(1)$，整体上也是 $O(n)$。

因此在一个空的可清空表上执行 $n$ 个操作的操作序列，在最坏情况下，整体的时间复杂度为 $O(n)$。

$\Box$

长为 $n$ 的操作序列在最坏情况下整体的时间复杂度为 $O(n)$，摊销到每一个操作就是 $O(1)$ 的时间复杂度。而对于一次特定的 clear 操作，最坏情况却是 $O(n)$。

一个操作的最坏时间复杂度是 $O(n)$，$n$ 个操作组成的操作序列整体的最坏时间复杂度还是 $O(n)$，这就是摊销分析的本意。

总结

本文我们通过一个简单例子初步了解了摊销分析的动机，以及具体是怎么做的。这一块深入讨论的话比较偏理论，设计到一些概念和推导，后续会继续跟大家分享。

在有了摊销分析的基础之后，我们就可以讨论伸展树、并查集等复杂数据结构的时间复杂度了。

Share