问题标签 [amortized-analysis]

如果在空的最小堆上，我们执行n任意插入和删除操作，（在最小堆中给定删除位置）。为什么插入O(1)和删除的摊销分析是O(log n)？

任何人都可以为我澄清吗？

当我跑到这个话题时。

我在本书第 5-1 页底部读到，二项式队列、斐波那契堆和倾斜堆具有 O(1) 的插入操作摊销成本和 O(log n) 的删除操作摊销成本。接下来作者写道，配对堆的插入操作摊销成本为 O(1)，删除操作的摊销成本为 O(log n)。

在此作业中，此链接上的第三 (3) 个分配和解决方案 没有定义堆的类型，写入 O(log n) 用于插入，O(1) 用于删除。

在这个作业中，另一位作者说二项式堆对于插入操作具有 O(log n) 和对于删除操作具有 O(1) 摊销成本。

问题是，哪一个是正确的？我很困惑。

我刚刚遇到这个问题，如果我们有一个动态分配的数组，则插入需要 O(1) 。但是当数组已满时，我们需要为数组重新分配双倍空间，因此复制旧数组需要 O(n)。

有什么办法可以使它成为 O(1)？

我读过一些关于可扩展数组的文章，但我并不理解它。任何人都可以帮助解释更多吗？

非常感谢。

在我的算法课上，我们讨论了摊销复杂度。不幸的是，由于参加体育比赛，我无法参加。在尝试联系教授解释这一点失败后，我被困在这里问了。什么是摊销复杂度，我如何找到它？我被分配了要做的工作，但不知道该怎么做。如果你们可以帮助我解决一个非常有帮助的问题或提供其他解释的参考。

这是问题所在：

假设没有溢出，考虑以下算法并将二进制数加 1，表示为 n 位数组：

这个算法在最坏的情况下显然是 O(n)。证明它的摊销复杂度是 O(1)。

我可以看到为什么最坏的情况是 O(n)，但我不知道为什么它的摊销复杂度是 O(1)。甚至就此而言，摊销复杂性是多少。

我遇到了一个本地竞赛问题，如下所示。

如果为空MIN-Heap，我们将执行n任意操作insert，delete（在最小堆中使用给定的删除位置）。什么是amortized analysisforinsert和delete？

I) 插入 O(log n)，删除 O(1)

II) 插入 O(log n)，删除 O(log n)

III) 插入 O(1)，删除 O(1)

IV) 插入 O(1)，删除 O(log n)

我认为这是这个问题的一个问题，因为没有定义堆的类型。我在谷歌上读到我们有一些堆的选项（1）和（4）。从专家的角度来看，我们可以用这个问题说can we select all options as True?

为什么时间复杂度是 O(n) 而不是 O(nlogn)？您不必将外循环的复杂性与内循环的复杂性相乘吗？

我发现 HaskellData.Vector.*错过了 C++std::vector::push_back的功能。有grow/ unsafeGrow，但它们似乎具有O(n)复杂性。

有没有办法在一个元素的O(1)摊销时间内增长向量？

当我在大学学习数据结构课程时，我学到了以下公理：

1. 在最坏的情况下，向堆中插入一个新数字需要O(logn)（取决于作为叶子插入时它在树中到达的高度）

2. 从一个空堆开始，使用n次插入，构建一个包含n 个节点的堆，使用分期分析将总和到O(n)时间

3. 在最坏的情况下，移除最小值需要O(logn)时间（取决于新顶部节点在与最后一个叶子交换后达到的低点）

4. 一个一个地去除所有最小值，直到堆为空，需要O(nlogn)时间复杂度

提醒： “堆排序”算法的步骤是：

• 将所有数组值添加到堆中：使用摊销分析技巧求和到O(n)时间复杂度
• 从堆中弹出最小值n次并将第i个值放在数组的第i个索引中：O(nlogn) 时间复杂度，因为在弹出最小值时摊销分析技巧不起作用

我的问题是：为什么在清空堆时摊销分析技巧不起作用，导致堆排序算法花费O(nlogn)时间而不是O(n)时间？

编辑/回答

当堆存储在一个数组中（而不是带有指针的动态树节点）时，我们可以自底向上构建堆，即从叶子开始到根，然后使用摊销分析我们可以得到总时间复杂度的O(n)，而我们不能清空堆最小值的自下而上。

假设我有一个堆栈，由一个 n 元素数组支持，推送成本为 1，从数组中取出一个元素的成本为 1，调整数组大小的成本是移动的元素数。

1）每次堆栈变满时，我都会将当前的 n 个元素复制到一个比以前大一个元素的新数组中。我的文字声称一系列 n 推送将导致总成本：

1 + 2 + 3 + ... + n

为什么是这样？假设我的数组从 n = 1 开始。

我推送，堆栈现在已满（成本 1）我增加数组的大小（n = 2 和成本 2）我推送并且堆栈现在已满（成本 1）我增加数组的大小（n = 3 和成本4) ...

我错过了什么？

2）假设每次堆栈已满时我都会将数组的大小加倍。现在我有一系列从 1 元素数组开始的 n 推送：

我推送，堆栈现在已满（成本为 1）我将数组大小加倍并复制 1 个元素（成本为 2，n = 2）我推送并且堆栈现在已满（成本为 1）我将数组大小加倍并复制 2元素超过（成本 4，n = 4）...

这个分析看起来对吗？

对于一系列 n 推送，它将产生 1 + 2 + 1 + 4 + 1 + 8 + ... + 1 + 2 ^ (n/2)

我想计算贷款摊销，但我不知道如何计算还款日期。

我有Loan amount, Interest rate, Monthly paymnet, Loan Start date. 从这四个值中，我想知道我在 iOS 中的贷款支付日期。

我数Interest，Monthly Amount就像

任何人都可以帮助我吗？