第 1 课｜动态数组与摊还分析
阅读提示：这是从聊天授课内容重构的课程讲义，不是原消息的逐字拷贝。建议先阅读概念动画，再跟随推导、数值算例和练习巩固知识。
学习问题
单次扩容会复制 O(n) 个元素，但容量翻倍使连续 m 次插入的总成本为 O(m)。
[[diagram:array]]
核心公式
\[amortized_cost_i = actual_cost_i + Φ(D_i) - Φ(D_{i-1})\]数值例题
容量 1 起始，复制数量依次为 1、2、4、8……；复制成本形成几何级数，小于 2m。加上 m 次插入，T(m)<3m。
推导、假设与边界
取势函数 Φ(n,C)=max(0,2n-C)，仅考虑从空数组开始的 push_back。普通插入的势能增加至多 2；满容量 k 时扩容，实际代价 k+1、势能从 k 降到 2，摊还代价正好为 3。非负势能与初始零势能使总真实成本不超过总摊还成本。
更进一步：势能法如何严格证明真实成本有界？
假设操作序列经历状态 $D_0,D_1,\ldots,D_m$，定义：
\[\hat c_i=c_i+\Phi(D_i)-\Phi(D_{i-1}).\]求和会出现望远镜消去：
\[\sum_{i=1}^m\hat c_i=\sum_{i=1}^m c_i+\Phi(D_m)-\Phi(D_0).\]如果初始势能为零并且始终非负，才能得到所需的方向：
\[\sum_i c_i\leq\sum_i\hat c_i.\]势能不是程序实际储存的内存，而是为了证明复杂度而设计的记账量。 它的合法性取决于对所有可达状态都满足下界要求。设计势函数的方向是：昂贵操作前能积累足够多的势能，昂贵操作发生时势能迅速下降。
一种反直觉情况：缩容为何可能造成抖动？
设旧容量为 $2k$，元素数为 $k+1$。删除一个元素后变成 $k$，立即缩容到 $k$，成本为 $\Theta(k)$。紧接着插入一个元素，因容量已满，又需扩容到 $2k$，成本也是 $\Theta(k)$。这两步使状态重新回到原点，因此可以任意重复。只要有 $\Theta(k)$ 轮，后续总成本就达到 $\Theta(k^2)$。
正确方向是滞回（Hysteresis）：满时扩容、低于四分之一才缩容，避免一增一删反复触发重分配。严格证明时仍需给出能同时覆盖插入和删除的势函数，并对四类状态转移逐一验证。
典型应用迁移
潜在“便宜操作存信用、昂贵操作消耗信用”的结构也出现在二进制计数器翻位、分层合并、队列扩缩容以及在线数据结构维护中。关键是一串操作的总成本，而不是期待每个操作都只花常数时间。
课后练习（暂不提供答案）
练习：把扩容倍数改为 1.5，再改为每次容量加 1，分析总复制次数的渐进复杂度。
后续学习
沿各门课 12 周知识树继续递进，必要时回顾本课基本概念。