摊还分析/平摊分析（Amortized Analysis）：从白痴到入门

2024-01-03 08:26| 来源: 网络整理| 查看: 265

什么是摊还分析？

摊还分析其实就是评价某一个操作的代价，方法就是求某数据结构中一系列操作的平均时间。摊还分析与概率无关，可以保证某一系列操作在最坏情况下的平均性能。

什么意思呢？举个例子，我们都知道栈这个数据结构，假设现在一个栈支持三种操作：

POP(S) //弹出栈顶元素 PUSH(S,x) //将元素x压如栈中 MultiPop(S,k) //将栈的前k个元素弹出

普通分析：

设栈为空栈，那么一系列操作，操作总数为n，分别执行PUSH(S,x), POP(S), MultiPop(S,k)操作，所以栈中最大元素数量为n。对于操作MultiPop(S,k)，最坏情况是 O ( n ) O(n) O(n)，因为容器最多含有n个元素。可以得出，对任意的栈的MultiPop(S,k)操作，最差时间复杂度都是 O ( n ) O(n) O(n)，那么要进行n个MultiPop(S,k)的操作，时间复杂度自然是 O ( n 2 ) O(n^2) O(n2)这种分析是对的，但是我们从常识得知，当我们第一次取出n个元素的时候，第二次以后的POP(S)操作时间复杂度就都是 O ( 1 ) O(1) O(1)了，所以我们的普通分析并不能更准确的求出时间复杂度。于是我们引入了摊还分析。

摊还分析

我们的POP(S)操作和MultiPop(S,k)操作只能在非空的栈上操作（也可以在空栈操作，最多返回null，但是这没意义）。也就是说，POP(S)能执行多少次，在于PUSH(S,x)了多少次。PUSH(S,x)了n次，那么POP(S)就只能操作n次。同理适用于MultiPop(S,k)对于任意的n，任意顺序的上述三种操作最多消耗O(n)时间。像一半操作PUSH一半操作POP。那么整体来说每个操作所以需时间为 O ( n ) / n = O ( 1 ) O(n)/n = O(1) O(n)/n=O(1)

上面看不懂没关系，下面才是重点。

问题引入

我们知道HashTable的查找时间复杂度是 O ( 1 ) O(1) O(1)，最差情况是 O ( n ) O(n) O(n)，这里我们认为一个HashTable是一个能够良好的解决冲突的，那么时间复杂度就是常数级别。这里就有一个问题：如何确定HashTable的最优大小？

我们的经验之谈，反正HashTable不管多大，查找时间都是常数级别，那么就让他越大越好咯。这句话本身没错，但是考虑到内存限制，我们不可能让它越大越好。现在语言中提供的API里，一般的解决方法都是给出一个固定大小的HashMap（如容量为8），当这个HashTable被填满或者填充到一定程度的时候，在对它进行动态扩容。一次扩容量为它的二倍。也就是原本为8个单位容量的表，满了后容量会变成16个单位，然后32个单位，64个单位…

上述提到的HashTable，我们会称为“动态表”(dynamic table)，那么为什么会以这个速率扩容呢？为什么不每次扩容一个固定值呢？毕竟固定值也好计算，不用再进行二进制逻辑左移位来做到二倍扩充。接下来我们分析内部逻辑。

动态表

我在前面提到，当表中数据满了，会以二倍的容量扩充。

如果我们自己手动实现一个HashTable，会发现扩充其实不那么容易。由于语言的限制，我们没法在原表扩充。比如C++的:

static int size = 1

【本文地址】

公司简介

联系我们