Amortized analysis
优质
小牛编辑
129浏览
2023-12-01
摊销分析涉及估计程序中的操作序列的运行时间,而不考虑输入值中的数据分布的跨度。 一个简单的例子是查找排序列表中的值比未排序列表中的值更快。 如果列表已经排序,则分布数据的方式无关紧要。 但是,当然列表的长度会产生影响,因为它决定了算法为获得最终结果而必须经过的步骤数。
因此,我们看到,如果获得排序列表的单个步骤的初始成本很高,则查找元素的后续步骤的成本变得相当低。 因此,摊销分析有助于我们找到一系列操作的最坏情况运行时间的界限。 摊销分析有三种方法。
Accounting Method - 这涉及为每个执行的操作分配成本。 如果实际操作比指定时间更快完成,则在分析中累积一些积极信用。 在相反的情况下,它将是负面信用。 为了跟踪这些累积的信用,我们使用堆栈或树数据结构。 早期执行的操作(如对列表进行分类)具有高摊销成本,但是随着累计信用的利用,顺序延迟的操作具有较低的摊余成本。 因此,摊销成本是实际成本的上限。
Potential Method - 在该方法中,保存的信用作为数据结构状态的数学函数用于将来的操作。 数学函数和摊销成本的评估应该相等。 因此,当实际成本大于摊销成本时,潜力会降低,并且它被用于昂贵的未来运营。
Aggregate analysis - 在此方法中,我们估计n步的总成本的上限。 摊销成本是总成本和步骤数(n)的简单划分。