摊还分析
简介
在分析算法时间复杂度的时候，往往有以下三种：
- 最坏情况分析 (Worst-case Analysis)
- 平均情况分析 (Average-case Analysis)
- 摊还分析 (Amortized Analysis)
一个算法的最坏运行时间给出了运行时间的上界；在某些特定情况下，也会对算法的平均运行时间感兴趣，但是平均情况分析的范围有限，因为对于特定的问题，算法输入的分布并不明显，很多时候常常假定给定规模（比如假设输入数组大小为
n
n
n）的所有输入具有相同的可能性，即输入的分布为均匀分布。
不同于最坏情况和平均情况分析只是针对某个单独的操作，摊还分析是求一个操作序列中所有操作的平均时间，即使某个单一操作的代价很高，但是只要它的平均代价低即可。不同于平均情况分析，摊还分析不涉及概率，它可以保证最坏情况下每个操作的平均性能。
初学时这段话不理解很正常，建议先看明白聚合分析中的案例后，再回过头来理解这段话
下面首先讲述摊还分析中最常用的三种技术，即聚合分析、核算法和势能分析，最后再对动态表进行摊还分析
本文内容是在学习了《算法导论》对摊还分析的讲解，总结出来的
聚合分析 (Aggregate Analysis)
所谓聚合分析，就是证明一个
n
n
n 个操作的序列最坏情况下花费的总时间为
T
(
n
)
T(n)
T(n)，然后我们就可以得到最坏情况下每个操作的平均代价，即摊还代价为
T
(
n
)
/
n
T(n)/n
T(n)/n。
注意这里的摊还代价
T
(
n
)
/
n
T(n)/n
T(n)/n 是适用于所有的操作的，哪怕序列中有不同类型的操作。而后面的核算法和势能法，可能会对不同类型的操作赋予不同的摊还代价。
栈操作
下面考虑对一个栈
S
S
S 的三种操作：
-
Push
(
S
,
x
)
\text{Push}(S, x)
Push(S,x): 将x
x
x 压入栈中 -
Pop
(
S
,
x
)
\text{Pop}(S, x)
Pop(S,x): 从栈顶弹出元素 -
MultiPop
(
S
,
k
)
\text{MultiPop}(S, k)
MultiPop(S,k): 从栈顶弹出k
k
k 元素
下面是
MultiPop
(
S
,
k
)
\text{MultiPop}(S, k)
MultiPop(S,k) 的伪代码实现
MultiPop(S, k):
while not S.is_empty() and k > 0:
Pop(S)
k = k - 1
下面来分析一个由
n
n
n 个
Push
\text{Push}
Push，
Pop
\text{Pop}
Pop 和
MultiPop
\text{MultiPop}
MultiPop 组成的操作序列在一个空栈上的最坏运行时间。由于
MultiPop
\text{MultiPop}
MultiPop 的最坏运行时间为
O
(
n
)
O(n)
O(n) （因为栈大小最大为
n
n
n），因此一个
n
n
n 个操作的序列的最坏情况代价为
O
(
n
2
)
O(n^2)
O(n2)。
但是这不是一个好的上界，通过聚合分析，我们可以得到一个更好的上界。
MultiPop
\text{MultiPop}
MultiPop 是由若干个
Pop
\text{Pop}
Pop 组成，在一个空栈上运行一个
n
n
n 个操作的序列，我们可以
Pop
\text{Pop}
Pop 的次数（包括
MultiPop
\text{MultiPop}
MultiPop 中的
Pop
\text{Pop}
Pop）最多和
Push
\text{Push}
Push 的数目一样，而
Push
\text{Push}
Push 的次数最多为
n
n
n， 因此最终
Push
\text{Push}
Push 和
Pop
\text{Pop}
Pop（包括
MultiPop
\text{MultiPop}
MultiPop 中的
Pop
\text{Pop}
Pop）的总次数最多为
2
n
2n
2n，故一个空栈上运行一个
n
n
n 个操作的序列的最坏情况代价为
O
(
n
)
O(n)
O(n)。所以摊还代价为
O
(
n
)
/
n
=
O
(
1
)
O(n)/n=O(1)
O(n)/n=O(1)。
在聚合分析中，每个操作的平均代价即为摊还代价，因此所有三种栈操作的摊还代价都为
O
(
1
)
O(1)
O(1)
所谓聚合分析，就是从整体上去求一个
n
n
n 个操作的序列在最坏情况下花费的总时间，具体怎么求，需要根据具体操作来进行分析，没有一个固定的思路
二进制计数器递增
下面来看一个
k
k
k 位二进制计数器递增的问题，计数器的初值为0。我们用一个位数组
A
[
0..
k
-1
]
A[0..k\text{-1}]
A[0..k-1] 作为计数器，其中
A
.
l
e
n
g
t
h
=
k
A.length=k
A.length=k。当计数器中保存的二进制值为
x
x
x 时，
x
x
x 的最低位保存在
A
[
0
]
A[0]
A[0] 中，最高位保存在
A
[
k
-1
]
A[k\text{-1}]
A[k-1] 中。下面是二进制计数器递增的算法。
Increment(A):
i = 0
while i < A.length and A[i] == 1:
A[i] = 0
i = i + 1
if i < A.length:
A[i] = 1
下面考虑对初值为0的计数器执行
n
n
n 个
Increment
\text{Increment}
Increment 操作的的最坏情况代价。显然该代价的一个上界为
O
(
n
k
)
O(nk)
O(nk)，但是可以得到一个更好的上界。
一次
Increment
\text{Increment}
Increment 操作的运行时间和翻转（0变为1，或者1变为0）的二进制位的数目呈线性关系，因此下面考虑对初值为0的计数器执行
n
n
n 个
Increment
\text{Increment}
Increment 操作，数组
A
A
A 中的位最多翻转的次数。我们可以手动执行一下
Increment
\text{Increment}
Increment 操作，不难发现，
A
[
0
]
A[0]
A[0] 每次调用
Increment
\text{Increment}
Increment 都会翻转，
A
[
1
]
A[1]
A[1] 每两次调用才会翻转一次，
A
[
2
]
A[2]
A[2] 每四次调用才会翻转一次，…。因此对于
n
n
n 个
Increment
\text{Increment}
Increment 操作，
A
[
i
]
A[i]
A[i] 翻转的次数为
⌊
n
/
2
i
⌋
\lfloor n/2^i\rfloor
⌊n/2i⌋，因此数组
A
A
A 中的位最多翻转的次数为
∑
i
=
0
k
−
1
⌊
n
/
2
i
⌋
<
n
∑
i
=
0
∞
1
2
i
=
2
n
\sum_{i=0}^{k-1}\lfloor n/2^i\rfloor<n\sum_{i=0}^{\infty}\frac{1}{2^i}=2n
∑i=0k−1⌊n/2i⌋<n∑i=0∞2i1=2n。
因此初值为0的计数器执行
n
n
n 个
Increment
\text{Increment}
Increment 操作的的最坏情况代价为
O
(
n
)
O(n)
O(n)，每个操作的摊还代价为
O
(
1
)
O(1)
O(1)。