Python - 摊销分析


分期分析包括估算程序中操作序列的运行时间,而不考虑输入值中数据分布的范围。一个简单的例子是在排序列表中查找值比在未排序列表中快。如果列表已经排序,则数据分布的方式无关紧要。但是,当然,列表的长度会影响算法,因为它决定算法必须经过的步骤才能获得最终结果。

因此,我们看到,如果获得排序列表的单个步骤的初始成本很高,则后续找到元素的步骤的成本变得相当低。因此,摊销分析有助于我们找到一系列操作的最坏情况运行时间的限制。分摊分析有三种方法。

  • 会计方法 - 这涉及为每个执行的操作分配成本。 如果实际操作比指定的时间更快结束,那么分析中会积累一些积极的信用。在相反的情况下,它将是负信贷。为了跟踪这些累计学分,我们使用堆栈或树形数据结构。早期进行的操作(如清单分类)具有较高的摊销成本,但随着积累的信用被利用,较晚的操作具有较低的摊销成本。所以摊余成本是实际成本的上限。

  • 潜在方法 - 在这种方法中,将保​​存的信用作为数据结构状态的数学函数用于将来的操作。 数学函数的评估和摊销成本应该是相等的。因此,当实际成本高于摊销成本时,潜在价值会下降,并且将用于未来昂贵的运营。

  • 综合分析 - 在这种方法中,我们估计n步骤总成本的上限。 摊销成本是总成本和步骤数(n)的简单划分。