平摊分析
平摊分析在计算机科学中,是用于算法分析中的方法,平摊分析常用于分析数据结构(动态的数据结构),在使用平摊分析前须知道数据结构各种操作所可能发生的时间,并计算出最坏情况下的操作情况并加以平均,得到操作的平均耗费时间。平摊分析只能确保最坏情况性能的每次操作耗费的平均时间,并不能确认平均情况性能。
一个简单的例子,一个长度为n的list,在list的最后要加入一笔新的资料此时要花费的操作时间为O(n),此时也是加入新的资料的最糟糕的情况。但是,一个 n 个插入的操作序列仍然可以在 O(n) 的时间内完成,因为剩下的插入可以在常数时间内完成,因此n 个插入可以在 O(n) 的时间内完成。因此每操作的平摊耗费为O(n) / n = O(1)。
注意平摊分析与平均时间分析和概率算法的概率分析不同。在平均时间分析中,我们平均化所有可能的输入;在概率算法的概率分析中,我们平均化所有可能的随机选择;在平摊分析中,我们平均化一系列操作的耗费。平摊分析假设的是最坏情况输入并且通常不运行随机选择。[1]
平摊分析中几种常用的技术:
平摊分析种类
聚集法(Aggregate method)
计算n个操作的时间复杂度上限T(n) 平摊T(n)至每一个操作,每一个操作的平摊成本是T(n)/n
记账法(Accounting method)
执行花费较低的operations时先存credit未雨绸缪, 供未来花费较高的operations使用
对每个操作定义一个合法的平摊成本(amortized cost) 假设 为第i个操作的actual cost, 为第i个操作的amortized cost
若 ,则credit= ,我们把credit存起来(deposited),未来可以提取(withdraw) 若 ,则提取credit
设置每个操作的平摊成本(amortized cost)后,要做valid check确保credit不可以是0,也就是说
位能法(Potential method)
定义一个位能函数(potential function) ,将数据结构D(例如: 堆栈)的状态对应到一个实数
- : 数据结构D的初始状态
- : 数据结构D经过 个操作后的状态
- : 第 个操作的actual cost
- : 第 个操作的amortized cost
定义
为了满足
我们定义 , 通常令 和
例子
堆栈(stack)的平摊分析
我们定义一个堆栈有下列操作
操作(operation) | 说明 | actual cost |
---|---|---|
S.push(x) | 将一个元素x放入堆栈S中 | |
S.pop() | 把堆栈S中最上面的元素取出 | |
S.multi-pop(k) | 一次pop k个元素 |
S.mult-pop(k)的代码如下
def multi_pop(k):
while (not S.empty()) and (k>0):
S.pop()
k -= 1
接下来我们分别使用聚集法(aggregate method), 记账法(Accounting method), 位能法(Potential method)求出"堆栈一个操作的平摊成本是O(1)"
使用聚集法(aggregate method)分析堆栈操作的平摊成本
令 是S.push(x)的执行次数, 是S.pop()的执行次数, 是S.multi-pop(k)的执行次数
- 为总执行次数
操作(operation) | actual cost | 执行次数 |
---|---|---|
S.push(x) | ||
S.pop() | ||
S.multi-pop(k) |
因为一个堆栈S如果是空的,就不能执行pop了,也就是说可以pop或multi-pop的元素个数不会超过S中push进去的元素个数
所以
假设 是执行 个操作的时间复杂度上限
所以堆栈一个操作的平摊成本为
使用记账法(Accouting method)分析堆栈操作的平摊成本
我们假设S.push(x), S.pop(), S.multi-pop(k)的amortized cost分别为2, 0, 0,如下表所示
操作(operation) | actual cost | amortized cost |
---|---|---|
S.push(x) | 1 | 2 |
S.pop() | 1 | 0 |
S.multi-pop(k) | 0 |
Valid Check
|
---|
|
因此每个操作的平摊成本是O(1)
使用位能法(potential method)分析堆栈操作的平摊成本
我们定义位能函数 为执行i个操作后,堆栈内的元素个数
- ,因为堆栈一开始是空的
- ,因为堆栈的元素个数一定
计算堆栈S每一个操作的平摊成本
操作(operation) | 平摊成本(amortized cost) |
---|---|
S.push(x) | |
S.pop() | |
S.multi-pop(k) |
总平摊成本 ,所以堆栈单一个操作的平摊成本是
动态数组
考虑一个随元素个数增加而增长的动态数组,比如Java的ArrayList或者C++的std::vector。如果我们的数组大小从4开始,那么来向其中增加四个元素的时间就是一个常数。然而,若要将第五个元素加入其中,那么会花费更多时间,因为我们此时必须要创建一个两倍于当前数组大小的数组(8个元素),把老元素拷贝到新数组中,然后增加一个新元素。接下来的三次加入操作也同样会花费常数时间,然后在数组被填满后则又需要一轮新的加倍扩充。
一般地,如果我们考虑任意一个任意的n大小的数组并对其进行n + 1次加入操作。我们注意到,所有的加入操作都是常数时间的,除了最后一个,它会花费 时间在大小加倍上。因为我们进行了n + 1次加入操作,我们可以将数组加倍的时间平摊到所有的加入操作上,因此得到加入操作的平均时间是 。它是一个常数。[1]
队列
使用Ruby实现的队列,一个先进先出数据结构:
class Queue
def initialize
@input = []
@output = []
end
def enqueue(element)
@input << element
end
def dequeue
if @output.empty?
while @input.any?
@output << @input.pop
end
end
@output.pop
end
end
队列操作及特性参考队列条目,enqeue及deqeue操作时间复杂度为常量, 否则,dequeue需要 时间将所有元素从输入数组添加到输出数组中,其中n是输入数组的当前长度。 从输入复制n元素后,我们可以在输出数组再次为空之前执行n出队操作,每次操作都需要一个恒定的时间。 因此,我们可以仅在 时间执行一系列n出列操作,这意味着每个出列操作的摊销时间是 。[2]
或者,我们可以收取将任何项目从输入数组复制到输出数组的成本,以及该项目的早期排队操作。 该计费方案将入队的摊还时间加倍,但将出列的摊还时间减少到 。
通常用法
- 在常见场合,我们把能很好平摊分析的算法称为“平摊算法”。
- 在线算法通常使用平摊分析。
参考资料
- ^ 1.0 1.1 1.2 1.3 1.4 Kozen, Dexter. CS 3110 Lecture 20: Amortized Analysis. Cornell University. Spring 2011 [14 March 2015]. (原始内容存档于2018-10-03).
- ^ Grossman, Dan. CSE332:Data Abstractions (PDF). cs.washington.edu. [2015年3月14日]. (原始内容存档 (PDF)于2015年4月2日).
- ^ MIT 6.046J Design and Analysis of Algorithms, Spring 2015. MIT. [2018-10-21]. (原始内容存档于2018-11-25).