问题标签 [amortized-analysis]

我有一个抽象数据类型，可以看作是从左到右存储的列表，有以下可能的操作： Push：向列表左端添加一个新项目 Pop：删除列表左端的项目 Pull ：删除列表右端的项目

使用三个堆栈和恒定的附加内存来实现这一点，以便任何推送、弹出或拉取操作的摊销时间都是恒定的。堆栈具有基本操作，isEmpty、Push 和 Pop。

摊销时间的意思是“如果我花这么多时间，我可以再花一部分时间，并将其存储在时间银行中以备后用。” 就像每次推送操作一样，花费三个常量时间块，所以对于每个推送的元素，你有 2 个额外的常量时间块。

我碰巧在维基百科上读到，在不相交集（联合两个元素，找到特定元素的父元素）上每次操作的摊销时间是 O(a(n))，其中 a(n) 是逆阿克曼函数，它会增长非常快。

谁能解释为什么这是真的？

例如，假设我有一个 O(n) 的算法和一个摊销 O(n) 的算法。公平地说，严格来说，非摊销算法总是比摊销算法快或快吗？或者是否有任何理由更喜欢摊销版本（忽略代码简单性或易于实现之类的东西）？

以下是wikipedia上不相交集森林的联合/查找算法的细分：

• 准系统不相交的森林... ( O(n))
  • ...按等级联合...（现在改进为O(log(n)）
    • ... 带有路径压缩（现在改进为O(a(n)), 有效O(1)）

按等级实现联合需要每个节点保留一个rank字段以进行比较。我的问题是，按等级联合是否值得这个额外的空间？如果我按等级跳过联合而只进行路径压缩会发生什么？够好吗？现在的摊销复杂度是多少？

做了一个评论，暗示没有路径压缩（摊销O(log(n)复杂性）的按等级联合对于大多数实际应用来说已经足够了。这是对的。我要问的是另一种方式：如果您按等级跳过联合并且只进行路径压缩怎么办？

从某种意义上说，路径压缩是按等级改进联合的额外步骤，这就是为什么可以省略该额外步骤而不会造成灾难性后果的原因。但是按等级联合是路径压缩的必要中间步骤吗？我可以跳过它并直接进行路径压缩，还是会是灾难性的？

还有人指出，如果没有按等级联合，重复联合可以创建类似链表的结构。这意味着单路径压缩操作可能会O(n)在最坏的情况下进行。这当然会影响未来的运营，所以当摊销到许多运营中时，这将如何发挥作用是我更感兴趣的。

举个简单的例子，在动态数组的具体实现中，每次数组填满时，我们将数组的大小加倍。因此，可能需要重新分配数组，在最坏的情况下，插入可能需要 O(n)。但是，一个序列的 n 次插入总是可以在 O(n) 时间内完成，因为其余的插入是在恒定时间内完成的，因此可以在 O(n) 时间内完成 n 次插入。因此，每次操作的摊销时间为 O(n) / n = O(1)。——来自维基

但是在另一本书中：每次加倍需要 O(n) 时间，但发生如此之少以至于它的摊销时间仍然是 O(1)。

希望有人能告诉我这种罕见的情况是否可以推断出 Wiki 的解释？谢谢

在阅读有关展开树的信息时，我发现了一些关于展开节点“X”的等级和维基百科中的摊销成本的表达。它给出为 { 我们可以通过以下方式限制任何锯齿形或锯齿形操作的摊销成本：

其中x是向根移动的节点，下标“f”和“i”分别表示操作之后和之前。当对整个展开操作求和时，它会伸缩到 3(rank(root))，即 O(log n)。由于最多有一个 zig 操作，这只会增加一个常数。}

我无法解释这一点。请有人详细解释上述内容。如果可能的话，举一些例子。

请提供一些链接以解释伸展树的其他定理

谢谢

我们如何分析 std::vector 后面的插入（push_back）？每次插入的摊销时间是 O(1)。特别是在Stephan T Lavavej 在第 9 频道的一段视频中，在这段视频中（从 17:42 开始），他说，为了获得最佳性能，微软对这种方法的实现将向量的容量增加了大约 1.5。

这个常数是如何确定的？

有一系列 n 次操作，如果 i 是 2 的精确幂，则第 i 次操作花费 2i，如果 i 是 3 的精确幂，则花费 3i，所有其他操作花费 1。

我已经使用聚合方法解决了它。为此，我将 2 的幂级数和 3 的幂级数相加，得到 10 的摊余成本。然后我使用会计方法对其进行了检查，对于非常长的序列，它并没有失败。但我的问题是如何证明它永远不会失败，我可以展示我想要的任意长序列，但它仍然不能保证它在一段时间后不会失败。

我也尝试用潜在函数方法解决它，这是我真正陷入困境的地方，要设置潜在函数我认为你需要非常有创意，我找不到一些条件表明此时这将始终成立，需要那里也有一些帮助。

只是一些关于如何在会计方法中证明它以及如何设计潜在功能的想法就足够了。谢谢

我有一个应用程序，可以有效地将向量用于代码的一部分。但是，在计算过程中，我需要跟踪一些元素。我听说您可以从 Data.Vectors 获得 O(n) 摊销连接（通过通常的数组增长技巧），但我认为我做得不对。所以假设我们有以下设置：

在这种情况下是否add在摊销的 O(n) 时间内运行？如果没有，我该怎么add做（我需要(forall s. MVector s Int)在州内存储一个吗？）。有没有更有效的实施方式add？

朋友们，我的教授涵盖了斐波那契堆并做了家庭作业。要求通常是在提取之后，我们需要通过链接相同程度的根来压缩根列表。我们使用数组索引来查找另一个相同度数的元素。但是现在假设您的系统中没有数组索引功能。使用一些数据结构和额外的指针实现提取，这样你就可以实现相同的摊销时间！！

我已经对此感到头疼，但我没有任何想法。任何线索或输入？？？