问题标签 [amortized-analysis]

我正在自学算法课程，我正在尝试解决以下问题：

描述一个存储一组实数的数据结构，它可以在 O(1) 的摊销时间内执行以下每个操作：

Insert(x) ：删除所有不大于 x 的元素，并将 x 添加到集合中。
FindMin() : 找到集合的最小值。

我意识到一旦你有了 Insert，findmin 就变得微不足道了，看看如何使用链表实现，你可以同时删除多个元素（即 O(1)），但找出要删除的链接（也就是 x 去哪里）似乎像 O(n) 或 O(log n) 操作，而不是 O(1)。问题给出了提示：考虑使用堆栈，但我看不出这有什么帮助。

任何帮助表示赞赏。

原始问题如下：

方法：维护两个堆栈A和B。压入A。弹出看B。如果B为空，则完全弹出A并将其压入B，然后从B弹出。否则只需从B弹出。

问题：1）运行时间和摊销运行时间有什么区别？2）为什么这里的摊销运行时间是常数？它不会随着输入数量的增加而增加吗？当我们决定从中弹出时？因为如果我们继续推动，那么 A 会填满很多，而 B 是空的。现在，如果我们决定从 B 中弹出，那么我需要复制所有 A，然后弹出。

我正在解决以下问题，来自我正在自学的课程的问题集。

我已经解决了第一部分。我被困在第二个。这些是我到目前为止的想法。我认为重建以 v 为根的子树的正确方法是遍历它一次以将值按排序顺序复制到数组中，然后再次遍历它以将其构建成平衡的二叉树。因此，这在 v.size 中是线性的。但是，我看不出势能和常数在哪里可以将其变成 O(1)，更不用说这样的常数如何取决于 alpha。正如我认为重建操作与 alpha 无关，而 alpha 只会影响您必须重建的频率？那么 alpha 会来自势函数吗？然后 c 只是用来取消阿尔法？如果是这样，我能否就如何重写潜在功能提供一些指导？

我已经阅读了一些关于摊销分析的帖子，但我在理解潜在方法方面仍然存在一些问题。

主要问题在于如何开发一个正式的势函数？以及如何评估势函数的正确性？

例如，有一个问题：

对数据结构执行一系列 n 操作。如果 i 是 2 的精确幂，则第 i 个操作的成本为 i，否则为 1。使用潜在方法来确定每次操作的摊销成本。

采用势函数，首先要提出一个势函数： . 有人告诉我，这很直观，但即使经过几个小时我也无法想出这个......

我发现有一个类似的问题：

需要使用势函数方法找到序列的摊销成本

但是，我认为答案是关于帐户方法的。

对于我们要查找的元素出现在其中的 2^n-1 个元素的排序数组的二进制搜索，摊销的最坏情况时间复杂度是多少？

在我的期末考试复习表上找到了这个。我什至无法弄清楚为什么我们需要分摊时间复杂度进行二分搜索，因为它最坏的情况是 O(log n)。根据我的笔记，摊销成本计算算法的上限，然后将其除以项目数，所以这不会像最坏情况下的时间复杂度除以 n 那样简单，即 O(log n )/2^n-1?

作为参考，这是我一直在使用的二进制搜索：

如果一个操作的摊销时间为 O(1)，那么在最坏的情况下，它可以花费 O(N^2) 时间吗？

我试图证明在排序的LinkedList 中插入操作的摊销复杂度是 O(1)。我知道最坏的情况时间是 O(n) 但很难找到合适的潜在函数。如果有人可以提供帮助，我会很高兴。

谢谢。

这属于 stackoverflow.com/help/on-topic 中的“软件算法”，在这种情况下，是一种将项目添加到动态未排序数组的软件算法

这是我们在课堂上制作的关于不同数据结构上的操作运行时间的图表

我的问题是关于将值插入（或添加）到动态未排序数组的运行时。这是我们执行此操作的代码

我理解这如何被解释为 O(n)。ensureCapacity 函数在技术上是由插入和运行时分析组成的操作的一部分，https://academics.tjhsst.edu/compsci/CS2C/U2/bigoh.html，你会说两个分支中最坏的情况是将原始数组的每个元素都复制到新数组中，这是一个 O(n) 操作。所以整个函数的最坏情况或大哦是O(n)

是否也可以为摊销 O(1) 时间提出论据（什么是算法的摊销分析？），因为每次调整大小时，都必须等待特定的时间才能进行下一次调整？

在那个图表中，那么 O(1) 也有意义吗？

最近去面试，面试官问了我这个问题。

有 k+1 堆大小1, 2^1, 2^2, 2^3, ...,2^k。让我们stack 1, stack 2, ... stack k+1分别称呼它们。当insert(x)被调用时，元素被插入第一个堆栈，即大小为 1 的堆栈。如果该堆栈已满，则该堆栈的元素被移动到下一个堆栈，然后元素被插入第一个堆栈。它类似于管道操作。堆栈 1 将元素推入堆栈 2，堆栈 2 推入堆栈 3，依此类推。如果所有堆栈都已满，那么我们会抛出一个错误，说明堆栈溢出。还有另一个操作，delete(x)。它从堆栈堆栈中删除 x。因此，如果 x 不是最顶部的元素，即它不存在于堆栈 1 中，则我们从中弹出元素，然后移动元素，然后再次尝试弹出，直到找到该元素并将其删除。插入和删除此实现的摊销复杂度是多少？

编辑 1：展示插入和删除的工作原理。
假设有 2 个堆栈，堆栈 1 和堆栈 2 的大小分别为 2^0 和 2^1。
迭代 0：堆栈 1 -> {}，堆栈 2 -> {}
迭代 1：插入（1）。堆栈 1 -> {1}，堆栈 2 -> {}，顶部 -> 1
迭代 2：插入（2）。堆栈 1 -> {2}，堆栈 2 -> {1}，顶部 -> 2
迭代 3：插入（3）。堆栈 1 -> {3}，堆栈 2 -> {2,1}，顶部 -> 3
迭代 4：插入（4）。溢出异常。堆栈 1 -> {3}，堆栈 2 -> {2,1}，顶部 -> 3
迭代 5：删除（2）。

• 我们弹出 3，作为 2!=3 并继续。堆栈 1 -> {2}，堆栈 2 -> {1}，顶部 -> 2
• 我们弹出 2 并返回。堆栈 1 -> {1}，堆栈 2 -> {}，顶部 -> 1
  迭代 6：插入（4）。Stack 1 -> {4}, Stack 2 -> {1}, top -> 3
  希望这两个操作现在都清楚了:)
  

我尽力而为，只能说出最坏情况的时间复杂度，即1+2^1+2^2+..+2^k（几何级数总和）。我不是在寻找最坏情况的时间复杂度。我什至无法达到摊销的复杂性。任何人都可以帮助理解如何计算这个问题的摊销复杂度吗？

我们希望有一组n线性列表来执行以下操作：

Insert(x,i)x：在列表中插入新元素i，此操作的成本为1。

Sum(i) :计算 list 中所有元素的总和，i并用计算的 替换list 中的所有元素，当我们使用此操作时sum，成本等于 list 中的元素数。i

如果我们从空列表开始并以任意方式进行上述操作，那么每个操作的摊销成本是多少：

谁能帮我理解如何解决这个例子，正确答案是什么？