平摊分析.PDF

算法设计与分析 平摊分析 汪小林 北大计算机系 主要内容 • 平摊分析的三种方法 – 聚集分析 – 记账法 – 势能法 • 动态表及其上的平摊分析 平摊分析 • 在平摊分析中，执行一系列数据结构操作所需要 的时间是通过执行的所有操作求平均而得出的。 平摊分析可以用来证明在一系列操作中，通过对 所有操作求平均之后，即使其中单一的操作具有 较大的代价，平均代价还是很小的。 • 平摊分析不牵涉到概率, 平摊分析保证在最坏情况 下，每个操作具有的平均性能。 平摊分析——聚集分析 栈S上的三种操作 • PUSH(S,x) ：将x压入S – 运行时间Ο(1) • POP(S) ：弹出栈顶 – 运行时间Ο(1) • MULTIPOP(S,k) ：弹出栈顶k个对象 MULTIPOP(S, k) 1 while not STACK-EMPTY(S) and k ≠ 0 2 do POP(S) 3 k → k - 1 – 运行时间Ο(min(k,s)) ，s为栈中对象个数 n个栈操作的平摊时间 • 设有n个栈操作（PUSH、POP 、MULTIPOP ） 的序列，作用于初始为空的栈S 。 • 总的运行时间的界是什么？ – 每个操作都可能是MULTIPOP – 每个MULTIPOP 的运行时间是Ο(min(k, s))=Ο(n) 2 – 总的运行时间的上界为Ο(n ) – 这是一个紧的上界吗？ n个栈操作的平摊时间 • 只有PUSH操作增加栈S 中的对象个数 • 所有POP和MULTIPOP 弹出的对象数不会弹出多 于PUSH入栈的对象数 • 故总的运行时间为Ο(n) – 所有PUSH入栈的对象数为Ο(n) – 所有POP和MULTIPOP 弹出的对象数也为Ο(n) • 每个PUSH 、POP和MULTIPOP 操作的平摊时间 – Ο(n)/n = Ο(1) • 聚集法：通过总运行时间求平均得到平摊时间， 不需要对操作序列的概率分布做假设。 二进制计数器 • 计数器A [0 ‥k -1] 表示为k位二进制位的数组 k 1  i x i 0 A i 2 • 操作INCREMENT实现计数器加一 – 运行时间Ο(k) INCREMENT(A) – n个INCREMENT操作 1 i ← 0 序列的运行时间 2 while i length [A ] and A [i] = 1 Ο(nk) （紧吗？） 3 do A [i] ← 0 4 i ← i + 1 5 if i length [A ] 6 then A [i] ← 1 INCREMENT操作的平摊时间 • n个INCREMENT操作序列 的运行时间应为：Ο(n) • 观察INCREMENT 操作序列 – 每次操作，A [0]都反转； – 每两次操作，A [1]反转； i – 每2 次操作，A [i]反转； • 于是，总反转次数为 log n  n  1    