聚合分析

概述

聚合分析（Aggregate Analysis）是摊还分析中最直接的方法，通过对 $n$ 个操作的总代价 $T(n)$ 确定一个上界，然后将总代价均摊到每个操作上，得到每个操作的摊还代价为 $T(n)/n$。在聚合分析中，所有操作被分配相同的摊还代价。

定义

聚合分析

给定数据结构上的 $n$ 个操作序列，聚合分析分两步进行：

1. 确定总代价的上界：$T(n)\le g(n)$
2. 每个操作的摊还代价为：$\hat{c}=g(n)/n$

其中 $g(n)$ 是总代价的渐近上界函数。所有操作共享相同的摊还代价 $\hat{c}$。

核心性质

1. 统一摊还代价：所有操作类型被分配相同的摊还代价，不区分不同操作的代价差异。这是聚合分析与记账方法、势能方法的关键区别。
2. 直接求和：核心思路是找到操作序列中”昂贵操作”被”廉价操作”补贴的规律，通过全局计数证明总代价有紧界。
3. 分析简单直观：三种摊还分析方法中，聚合分析通常是最容易理解和应用的，适合操作类型单一或代价差异不大的场景。
4. 无法区分操作类型：当不同操作的实际代价差异很大时，聚合分析可能给出不够紧的界，因为它对所有操作一视同仁。

经典例子

栈操作（MULTIPOP）

考虑一个栈，支持三种操作：

• PUSH(S, x)：将元素 $x$ 压入栈 $S$，代价 $O(1)$
• POP(S)：弹出栈顶元素，代价 $O(1)$
• MULTIPOP(S, k)：连续弹出栈顶 $\min (k,|S|)$ 个元素，代价 $O(\min (k,|S|))$

分析：在一个由 $n$ 个 PUSH、POP、MULTIPOP 组成的操作序列中，每个元素最多被压入一次。因此，POP 和 MULTIPOP 的总弹出次数==不超过 PUSH 的总次数 $n$==。

$T(n)=\underset{\text{PUSH 代价}}{\underbrace{O(n)}}+\underset{\text{POP + MULTIPOP 代价}}{\underbrace{O(n)}}=O(n)$

每个操作的摊还代价为 $T(n)/n=O(1)$。

二进制计数器

考虑一个 $k$ 位二进制计数器，初始值为 0，支持 INCREMENT 操作（加 1）。

分析：INCREMENT 翻转的位数等于从最低位起连续 1 的个数加 1。观察规律：

• 第 $i$ 位（从 0 开始）在 $n$ 次 INCREMENT 中最多翻转 $\lfloor n/2^i\rfloor$ 次
• 总翻转次数： ${\sum }_{i=0}^{k-1}\lfloor n/2^i\rfloor <n{\sum }_{i=0}^{\infty }1/2^i=2n$

因此 $n$ 次 INCREMENT 的总代价为 $O(n)$，每次操作的摊还代价为 $O(1)$。

局限性

• 无法区分操作类型：当序列中存在多种操作且代价差异大时，统一摊还代价可能掩盖某些操作的昂贵性
• 上界可能不够紧：相比记账方法和势能方法，聚合分析有时只能给出较松的界
• 灵活性最低：三种方法中，聚合分析的灵活性最弱，无法为不同操作分配不同的摊还代价

不相交集合链表表示（加权合并）

在 不相交集合数据结构 的链表表示中，使用 加权合并启发式 后，$m$ 次 MAKE-SET + UNION 操作的总代价上界为 $O(m+n\lg n)$。

分析：每个对象最多被移动到新列表头部 $O(\lg n)$ 次（因为每次合并后所在集合大小至少翻倍），因此 $n$ 个对象的总移动次数为 $O(n\lg n)$。加上 $m$ 次 MAKE-SET 的 $O(m)$ 代价，总代价为 $O(m+n\lg n)$，每次操作摊还 $O(1)$（当 $m=\Omega (n\lg n)$ 时）。

参见

• 摊还分析 — 聚合分析所属的总体分析框架
• 16.2 记账方法 — 支持不同操作不同摊还代价的方法
• 16.3 势能方法 — 最灵活的摊还分析方法
• 16.4 动态表 — 聚合分析的应用案例之一
• 不相交集合数据结构 — 聚合分析的应用案例
• 加权合并启发式 — 链表表示中的优化策略