摊销复杂度和平均复杂度有什么区别？在使用链表和数组实现堆栈时，什么是加倍和增量策略？
问问题
2888 次
1 回答
2
通常，平均情况复杂度和摊销复杂度指的是不同的概念。在描述平均情况下随机算法或数据结构的运行时间时，通常使用平均情况复杂度。例如，我们可以讨论随机快速排序的平均情况运行时间（其中枢轴是随机选择的），或跳过列表的平均情况运行时间。
另一方面，摊销复杂度通常是指某些系列操作完成的总工作量除以执行的操作总数的比率。例如，在一个动态数组中，只要需要更多空间，它的大小就会翻倍，每个单独的追加操作可能会做 O(n) 的工作来复制数组和传递元素。但是，这样做会使接下来的 n 个操作在 O(1) 时间内完成，因为保证空间可用。因此，任何 n 个追加都需要 O(n) 总时间，因此每个操作的摊销成本为 O(1)；这是总工作量 (O(n)) 与操作数 (n) 的比率。
这两个概念可能看起来相似，但它们代表着根本不同的概念。平均复杂度是指考虑到运行时的潜在概率分布，平均工作量。摊销复杂度是指基于某些操作“昂贵”但可以通过“更便宜”操作支付的事实，由一系列操作完成的平均工作量。这就是为什么某些数据结构（例如，具有重新散列的链式哈希表）的操作在平均情况下需要 O(1) 分摊时间 - 平均而言，数据结构上的任何 n 个操作序列将花费 O(n) 时间.
至于您的下一个问题 - 加倍与增量增长 - 加倍策略可确保推送操作的 O(1) 摊销复杂性，而增量增长策略则不能。直观地说，如果在需要更多空间时将数组的大小加倍，那么在将 n 个元素复制到大小为 2n 的数组之后，接下来的 n 次推送将是“便宜的”，因为空间将是可用的。因此，任何一系列的 n 次操作都需要 O(n) 时间，所有操作都需要平均 O(1) 时间。通过一些更复杂的数学，您可以证明任何大于 1 的因子的增长都会导致 O(1) 摊销时间。
另一方面，增量增长并不能保证这一点。这样想——如果你通过向数组添加 k 个元素来增长并且拥有一个大小为 10000k 的数组，那么在增长时你将做 10000k 的工作以使下一个 k 操作更快。在“便宜”地完成这些 k 操作之后，您必须做 10001k 工作才能再次增长数组。您可以证明这将需要 Θ(n 2 ) 在一系列 n 推动上工作，这就是不推荐它的原因。
最后，您询问了数组与链表的关系。使用链表时，您无需担心加倍或增量增长，因为您可以有效地（在 O(1) 中）分配新的链表单元并将它们链接起来。它们是最坏情况下的有效结构，而不是摊销有效结构，尽管常数因子更高。
希望这可以帮助！
于 2013-09-01T20:06:38.250 回答