介绍

• 在摊还分析中，我们求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价。它并不涉及概率，可以保证最坏情况下每个操作的平均性能。

• 介绍三种方法：聚合分析、核算法、势能法。

• 通过做摊还分析，通常可以获得对某种特定数据结构的认识，这种认识有助于优化设计。

17.1 聚合分析

• 利用聚合分析，我们证明对所有n，一个n个操作的序列最坏情况下花费总时间为T(n), 因此每个操作的摊还代价为T(n)/n

• 对任意n值，任意一个由n个PUSH、POP和MULTIPOP组成的操作序列，最多花费O(n)时间，一个操作的平均时间为O(n)/n = O(1)

• 对一个初值为0的计数器，执行一个n个INCREMENT操作的序列的最坏情况时间为O(n), 每个操作的摊还代价为O(1)

• 练习17.1-1 If the set of stack operations included a MULTIPUSH operation, which pushes k items onto the stack, would the O(1) bound on the amortized cost of stack operations continue to hold?

摊还代价现在是O(k)

• 练习17.1-2 Show that if a DECREMENT operation were included in the k-bit counter example, n operations could cost as much as theta(nk) time.

1000->0111->1000 ...
这样n个操作可以耗费Theta(nk)时间。

• 练习17.1-3 A sequence of n operations is performed on a data structure. The ith operation costs i if i is an exact power of 2, and 1 otherwise. Use aggregate analysis to determine the amortized cost per operation.

n个操作的总代价为 1+2+1+4+1+1+1+8+1+1+1+1+1+1+1+16... = 2n
故摊还代价为O(1)

17.2 核算法

• 用核算法进行摊还分析时，我们对不同操作赋予不同的费用。将赋予一个操作的费用称为它的摊还代价。这种方法不同于聚合分析中所有操作都赋予相同摊还代价的方式。

• 必须确保序列总摊还代价始终是序列总真实代价的上界。这要对于所有操作序列都成立。(关联的信用始终非负)

• 二进制计数器：对于置位操作，将摊还代价设为2美元，1美元为实际代价，一美元为信用用于支付将来复位的操作代价。INCREMENT过程至多置位一次。因此对于n个INCREMENT操作，总摊还代价为O(n)，为总代价的上界。

• 练习17.2-1 Suppose we perform a sequence of stack operations on a stack whose size never exceeds k. After k operations, we make a copy of the entire stack for backup purposes. Show that the cost of n stack operations, including copying the stack is O(n) by assigning suitable amortized costs to the various stack operations.

插入赋4
删除消耗1
复制消耗1
n次操作至少有n/2次插入，因此总信用不会为负。

• 练习17.2-2 Redo Ex 17.1-3 using an accounting method of analysis.

每次操作赋3.(refer to dynamic tables)

• 练习17.2-3 Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bits in it 0). Counting the time to examine or modify a bit as O(1), show how to implement a counter as an array of bits so that any sequence of n INCREMENT and RESET operations takes time O(n) on an initially zero counter. (Hint: Keep a pointer to the high-order 1.)

感觉如果维护一个指针指向最高位的一，
这就和普通的二进制计数器没什么差别了
修改一下读取数的方法就行
就算数组是11111111111，如果指针指向最右边一位
那么读到的数是1

17.3 势能法

• 势能法摊还分析并不将预付代价表示为数据结构中特定对象的信用，而是表示为势能，将势能释放即可用来支付未来操作的代价。我们将势能与整个数据结构相关联。

• 每个操作的摊还代价等于实际代价加上此操作引起的势能变化。如果势差为正，则第i个代价多付费，反之少付费，势减少用于支付实际代价。

• 如果初始势为0，那么势要永远非负。这样就能保证n个操作的总摊还代价为总实际代价的上界。

• 练习17.3-1 假设有势函数初始D0不为0，且对所有i满足Di>=D0,试证明存在势函数D’,使得D’0=0,对所有i满足D’i>=0,且用两种势函数摊还代价相同。

不管D是怎么定义的，定义D'为D-D0.

• 练习17.3-2 用势能法重做练习17.1-3

设 i = 2 ^ j + k, 定义势函数为2 ^ k

• 练习17.3-3

• 练习17.3-4

• 练习17.3-5

• 练习17.3-6

• 练习17.3-7

17.4 动态表

• 研究动态扩张和收缩表问题

• 表扩张

TABLE-INSERT(T, x)
    if T.size == 0
        allocate T.table with 1 slot
        T.size = 1
    if T.num == T.size
        allocate new-table with 2 * T.size slots
        insert all items in T.table into new-table
        free T.table
        T.table = new-table
        T.size = 2 * T.size
    insert x into T.table
    T.num += 1

n个TABLE-INSERT操作的总代价<3n
用三种方法分析均可。

• 表扩张和收缩。我们希望保持: 动态表的装载因子有一个正的常数下界, 一个表操作的摊还代价有一个常数上界。

• 当向一个满表插入一个新数据项时，我们仍然将表规模加倍，但只有装载因子小于1/4,才将表规模减半。

• 势函数真的难找= =