合并操作的摊销成本

计算合并操作的摊销成本是一项艰巨的任务。最大的困难在于根据随机的操作序列中不同操作成本的差异进行累加。虽然我们的设计目标会受到操作序列成本的影响，但根据操作序列成本定义操作摊销成本的概念却没有任何帮助。通过实现一个潜在函数来抵消实际成本的差异是处理这种情况的一种完美方式。在下一主题中，我们讨论摊销成本的概念。

令 B 是基本运算 P = {P₁, P₂,……, P_k} 的抽象数据类型 (ADT)，令 DS 是实现 B 的数据结构。令 F 是指定在数据结构配置到非负实数的潜在函数。进一步令 F(Φ) = 0。令 DS^j 指定我们针对配置 DS 执行操作 Pk 而获取的配置，令 C 表示针对 DS 执行 Pk 的实际成本。

然后，Pk 在 DS 上运行的摊销成本表示为 a(Pk, DS)，由下式给出

a(P_k, DS) = C + F(DS^j) – F (DS)

如果对所有大小为 m 的配置 DS，a(P_k, DS)≤ cjg(m)，则我们得出 Pk 的摊销成本为 O(g(m))。

阿纳布·查克拉博蒂

更新时间：2020 年 1 月 2 日

282 次查看

开启您的 职业生涯

完成课程获得认证

开始