全部教程· Python语言· Python数据结构 · Python 摊销分析

Python 摊销分析

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

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

会计方法 - 这涉及为每个执行的操作分配成本。如果实际操作比指定的时间更快结束，那么分析中会积累一些积极的信用。在相反的情况下，它将是负信贷。为了跟踪这些累计学分，我们使用堆栈或树形数据结构。早期进行的操作（如清单分类）具有较高的摊销成本，但随着积累的信用被利用，较晚的操作具有较低的摊销成本。所以摊余成本是实际成本的上限。
潜在方法 - 在这种方法中，将保存的信用作为数据结构状态的数学函数用于将来的操作。数学函数的评估和摊销成本应该是相等的。因此，当实际成本高于摊销成本时，潜在价值会下降，并且将用于未来昂贵的运营。
综合分析 - 在这种方法中，我们估计n步骤总成本的上限。摊销成本是总成本和步骤数（n）的简单划分。

下一章：Python 算法理由

为了使算法的效率更高效，我们需要一些数学工具作为证明。这些工具可帮助我们提供有关算法性能和准确度的数学上令人满意的解释。下面列出了一些可用于将一种算法转换为另一种算法的数学工具。直接证明：这是通过使用直接计算直接验证 ...

下一章：Python 算法理由