熔炼经营摊销成本

2024-04-22 19:53:06 328

计算熔合操作的摊销成本是一项艰巨的任务。主要的困难是要积累在随机操作序列中不同点执行的操作成本的巨大差异。尽管我们的设计目标受工序序列成本的影响，但根据工序序列成本来定义摊销成本的概念没有任何意义。实现潜在功能以设置实际成本的差异是处理这种情况的理想方法。在下一个主题中，我们讨论摊销成本的概念。

设B为基本操作P={P₁，P₂，……，P_k}的抽象数据类型(ADT)，使DS为实现B的数据结构。令F为在B的配置上指定的潜在函数。数据结构为非负实数。进一步让F（Φ）=0。令DS^j指定如果我们在配置DS上执行操作Pk所获得的配置，并且让C表示在DS上执行Pk的实际成本。

然后，在DS上运行的Pk的摊销成本表示为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)）。