79

有人可以用外行的术语解释摊销的复杂性吗？我一直很难在网上找到一个精确的定义，我不知道它与算法分析有什么关系。任何有用的东西，即使是外部引用的，都会受到高度赞赏。

4

6 回答 6

101

摊销复杂度是每个操作的总费用，在一系列操作中评估。

这个想法是保证整个序列的总费用，同时允许单个操作比摊销成本高得多。

示例：
C++ 的行为std::vector<>。当push_back()向量大小增加到超过其预先分配的值时，它会加倍分配的长度。

所以单个push_back()可能需要O(N)时间来执行（因为数组的内容被复制到新的内存分配中）。

但是，由于分配的大小增加了一倍，下一次N-1调用push_back()will 每次都需要O(1)时间来执行。所以，总的N操作还是需要O(N)时间的；从而给出每次操作push_back()的摊销成本。O(1)

除非另有说明，否则摊销复杂度是任何操作序列的渐近最坏情况保证。这表示：

  • 与非摊销复杂性一样，用于摊销复杂性的大 O 表示法忽略了固定的初始开销和恒定的性能因素。因此，为了评估 big-O 摊销性能，您通常可以假设任何摊销操作序列将“足够长”以摊销固定的启动费用。具体来说，对于这个std::vector<>例子，这就是为什么你不需要担心你是否真的会遇到N额外的操作：分析的渐近性质已经假设你会遇到。

  • 除了任意长度之外，摊销分析不会对您正在测量其成本的操作序列做出假设——它是对任何可能的操作序列的最坏情况保证。无论操作选择得多么糟糕（例如，被恶意对手！），摊销分析必须保证足够长的操作序列的成本可能不会始终超过其摊销成本的总和。这就是为什么（除非作为限定词特别提到）“概率”和“平均情况”与摊销分析无关——就像它们与普通的最坏情况大 O 分析无关一样！

于 2013-02-26T01:18:43.543 回答
33

在摊销分析中，执行一系列数据结构操作所需的时间是所有执行操作的平均值……摊销分析与平均情况分析的不同之处在于不涉及概率。摊销分析保证了在最坏情况下每个操作的平均性能。

（来自 Cormen 等人，“算法简介”）

这可能有点令人困惑，因为它既说时间是平均的，也不是平均情况分析。所以让我试着用一个金融类比来解释这一点（事实上，“摊销”是一个最常与银行和会计相关的词。）

假设您正在经营彩票。（不是购买彩票，我们稍后会谈到，而是自己操作彩票。）您打印 100,000 张彩票，每张以 1 个货币单位出售。其中一张门票将使购买者有权获得 40,000 个货币单位。

现在，假设您可以出售所有门票，您将获得 60,000 个货币单位：100,000 个货币单位的销售额，减去 40,000 个货币单位的奖金。对您来说，每张票的价值是 0.60 个货币单位，摊销在所有票上。这是一个可靠的值；你可以依靠它。如果您厌倦了自己卖票，而有人过来并提出以每张 0.30 货币单位的价格出售，那么您确切地知道自己的立场。

对于彩票购买者来说，情况就不同了。购买者在购买彩票时预期损失 0.60 个货币单位。但这是概率性的：购买者可能会在 30 年内每天购买 10 张彩票（略多于 100,000 张）而从未中奖。或者他们可能有一天会自发地购买一张票，并赢得 39,999 个货币单位。

应用于数据结构分析，我们谈论的是第一种情况，我们将某些数据结构操作（例如插入）的成本摊销到所有此类操作中。平均案例分析处理随机操作（例如搜索）的预期值，我们无法计算所有操作的总成本，但我们可以提供单个操作的预期成本的概率分析。

人们经常说，摊销分析适用于高成本操作很少见的情况，而且情况经常如此。但不总是。例如，考虑所谓的“银行家队列”，它是一个先进先出 (FIFO) 队列，由两个堆栈组成。（这是一个经典的函数式数据结构；你可以用不可变的单链接节点构建廉价的 LIFO 堆栈，但廉价的 FIFO 并不那么明显）。操作实现如下：

put(x):  Push x on the right-hand stack.
y=get(): If the left-hand stack is empty:
           Pop each element off the right-hand stack and
             push it onto the left-hand stack. This effectively
             reverses the right-hand stack onto the left-hand stack.
         Pop and return the top element of the left-hand stack.

现在，我声称 和 的摊销成本put是get，O(1)假设我以空队列开始和结束。分析很简单：我总是put进右手边的栈，然后get从左手边的栈中。因此，除了If子句之外， eachput是 a push， eachget是 a pop，两者都是O(1)。我不知道我会执行多少次If子句——它取决于puts 和gets 的模式——但我知道每个元素从右侧堆栈移动到左侧堆栈恰好一次。put因此，整个 n s 和 n s序列的总成本get为： n pushes、n pops 和 n moves，其中 amove是 apop后跟 a push：换句话说，2n 次操作（n puts 和 n gets）导致 2n pushes 和 2n pops。所以单的摊销成本put还是get一push加一pop。

请注意，银行家队列之所以被称为正是因为摊销复杂性分析（以及“摊销”一词与金融的关联）。银行家的队列是过去常见面试问题的答案，尽管我认为它现在被认为太知名了：想出一个在摊销 O(1) 时间内实现以下三个操作的队列：

1) 获取并移除队列中最旧的元素，

2）将一个新元素放入队列中，

3) 求当前最大元素的值。

于 2013-02-26T01:28:25.343 回答
23

“摊销复杂性”的原则是，虽然做某事时可能相当复杂，但由于不经常做，所以被认为是“不复杂”。例如，如果您创建一棵不时需要平衡的二叉树 - 比如说每次2^n插入一次 - 因为虽然平衡树非常复杂，但它只会在每 n 次插入中发生一次（例如，在插入编号 256 处发生一次，然后在第 512、1024 等）。在所有其他插入中，复杂度为 O(1) - 是的，每 n 次插入需要 O(n) 一次，但这只是1/n概率 - 所以我们将 O(n) 乘以 1/n 并得到 O(1)。所以这被称为“O(1) 的摊销复杂度”——因为当你添加更多元素时，重新平衡树所消耗的时间是最少的。

于 2013-02-26T00:45:48.650 回答
6

摊销意味着在重复运行中分配。保证最坏情况的行为不会频繁发生。例如，如果最慢的情况是 O(N)，但发生这种情况的机会只有 O(1/N)，否则过程是 O(1)，那么算法仍然有摊销常数 O(1) 时间. 只需考虑将每个 O(N) 运行的工作分配给其他 N 运行。

这个概念取决于有足够的运行来划分总时间。如果算法只运行一次，或者每次运行都必须在最后期限内完成，那么最坏情况的复杂性就更重要了。

于 2013-02-26T00:47:07.690 回答
4

假设您正在尝试查找未排序数组的第 k 个最小元素。对数组进行排序将是 O(n logn)。因此，找到第 k 个最小的数字只是定位索引，所以 O(1)。

由于数组已经排序，我们再也不需要排序了。我们永远不会多次遇到最坏的情况。

如果我们执行 n 次尝试定位第 k 个最小的查询，它仍然是 O(n logn)，因为它优于 O(1)。如果我们平均每个操作的时间，它将是：

(n logn)/n 或 O(logn)。因此，时间复杂度/操作次数。

这是摊销的复杂性。

我觉得是这样的，我也在学习。。

于 2014-06-21T07:26:53.727 回答
2

它有点类似于将算法中不同分支的最坏情况复杂度乘以执行该分支的概率，然后将结果相加。因此，如果某个分支不太可能被采用，那么它对复杂性的贡献就较小。

于 2013-02-26T00:47:10.670 回答