去摊还化

目标与不变量 ​

摊还分析公理库摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。只保证长度为 $m$ 的合法序列总成本至多 $mT$，单次操作仍可能花 $\mathrm{\Theta }(n)$。去摊还化重新安排同一批工作，使每次公开操作都在最坏 $O(T)$ 或指定预算内完成。

常用构造维护旧结构 $D_0$、正在生成的新结构 $D_1$ 和待迁移工作队列。每次用户操作除本职工作外再执行至多 $c$ 个迁移步骤。完成前保持：未迁移元素仍可由 $D_0$ 找到；已迁移元素以 $D_1$ 为准；迁移期新更新同时写入两侧或进入按序日志。查询据此检查权威版本。

增量扩容的账 ​

容量 $n$ 的动态数组装满后申请 $2n$ 新区，不一次复制 $n$ 项，而让随后每次插入搬两项。未来至少还能插入 $n$ 项才再次装满，因此搬迁在 $n/2$ 次操作内结束，早于下一次扩容；一次插入承担常数写入，得到最坏 $O(1)$ 延迟。

覆盖尚未迁移的下标后，旧副本必须更新或记录新值，否则稍后复制会让旧值复活。若每步只搬一项而每次更新制造两个待迁移项，积压持续增长，“每步做一点”并未给最坏界。

边界 ​

去摊还化不是从任意摊还证明自动生成。工作必须能切成保持可查询状态的微步，旧版与新版能在受控空间内并存，迁移处理率还要追上新任务的到达率。下一次重建若在旧迁移结束前触发，双结构会叠成三结构，原空间与延迟界都需重新证明。

确定性每步预算才能给 deterministic worst-case；重建规模或迁移进度只以高概率受控时，只能声称 high-probability worst-case。后台线程若可能被调度器长期饿死，抽象工作量界也不能直接解释为 wall-clock 截止期。

写入并发时的版本协议 ​

迁移期间把每个逻辑槽分成“尚未复制、正在复制、已经复制”三态。写操作先读取状态：尚未复制时同时更新旧值和一条 redo 记录；正在复制时用短锁或版本号防止复制线程读到撕裂值；已经复制时只写新结构。复制步骤在发布新值前再次检查版本，若期间发生写入就重放最新记录。这样可在线性化点上解释每次读写，而不只是最终集合相等。

删除也不能简单清空旧槽。若复制线程已经读出元素、尚未写入新区，删除须留下 tombstone 并让复制提交前检查；否则被删元素会复活。使用双写则省日志读取，却把每次更新常数和缓存写流量增大，属于实现权衡。

成本与空间全账 ​

若普通操作成本 $T(n)$，每步迁移预算 $c$，公开最坏成本为 $T(n)+O(c)$。启动复制需分配新区，若内存初始化本身线性，就必须依赖惰性页映射或把初始化也拆成任务。空间在旧区、新区与日志并存时为两份结构加积压，不能只报告稳态空间。

对动态数组例子，复制 $n$ 项、每次搬 2 项，最多 $\lceil n/2\rceil$ 次插入完成。即使插入同时增加一个新元素，复制工作总到达率仍为 0，只有固定初始 $n$；对增量 rehash，每次插入还可能制造桶工作，必须重新计算到达率。

与实时和摊还保证的分界 ​

摊还 (O(1)) 允许一次 (\Theta(n))，去摊还后的确定性最坏 (O(1)) 排除这种算法级尾延迟；“以高概率每次 (O(1))”仍允许小概率超时，不能替代硬实时保证。

参考资料

• Mark Overmars, The Design of Dynamic Data Structures, Springer, 1983.
• Paul Dietz, Daniel Sleator, “Two Algorithms for Maintaining Order in a List,” STOC 1987.
• MIT 6.851, Advanced Data Structures, deamortization notes.