每日科普 · 2026-10-28 周三

考研 408 × 求职面试

知识点 · 算法设计与分析 · 进阶

摊还分析：聚集分析、记账法与势能法

摊还分析不是算单次最坏，而是看一串操作的总代价再分摊到每次，适合动态数组扩容、栈操作、并查集等。
1. 聚集分析：先求 n 次操作总代价上界，再除以 n。例如动态数组容量翻倍，n 次插入总代价 O(n)，所以摊还 O(1)。
2. 记账法：给每次操作预存“虚拟货币”，便宜操作多收一点，昂贵操作用存款支付；只要任何前缀存款不为负，摊还界成立。
3. 势能法：定义非负势函数 Φ，令摊还代价=实际代价+Φ(后)-Φ(前)。总摊还=总实际+Φ(n)-Φ(0)，若 Φ 非负且初值为 0，则总实际不超过总摊还。
三种方法本质等价，考试常要求分别证明同一个结构的摊还复杂度。

每日一题 · 算法设计与分析

摊还分析：聚集分析、记账法与势能法

对初始容量为1、满时容量翻倍的动态数组，连续执行 n 次 push_back（不考虑删除），请用聚集分析说明其摊还代价为 O(1)。

解析

设第 i 次扩容复制 i 个旧元素。n 次插入中扩容发生在 1,2,4,...，复制总代价 1+2+...+2^k<2n；加上 n 次插入基本代价 n，总代价<3n。因此摊还代价=(总代价)/n<3=O(1)。注意扩容那次单次最坏是 O(n)，但摊还看整个序列。

面试小贴士 · 算法设计与分析

摊还分析：聚集分析、记账法与势能法

面试常问：动态数组 push_back 为何摊还 O(1)？摊还与平均有何区别？答题先声明看操作序列总代价，再选聚集、记账或势能之一证明；强调非概率平均。易错：只算单次、忘复制成本、势函数取负或初值不为 0。

代码实现 · C++

代码示例

#include <iostream>
using namespace std;
int main() {
    int n = 16, cap = 1, size = 0, total = 0;
    for (int i = 0; i < n; ++i) {
        if (size == cap) {
            total += size; // 扩容复制旧元素
            cap *= 2;
        }
        total += 1; // 插入新元素
        ++size;
    }
    cout << "n=" << n << ", total=" << total
         << ", amortized=" << (double)total / n << endl;
    return 0;
}