问题标签 [amortized-analysis]

从TimeComplexity的文档中可以看出，Python 的list类型是使用数组实现的。

因此，如果正在使用一个数组并且我们进行了一些附加操作，最终您将不得不重新分配空间并将所有信息复制到新空间。
毕竟，它怎么可能是 O(1) 最坏的情况？

优先级验证器支持操作、插入、删除和 not-all-bigger(z)。后一种操作输出“是”，前提是当前集合中有一个元素的键≤ z，否则输出“否”。z 由用户提供。当集合中有 n 个元素时，是否可以实现优先级验证器以使其操作具有摊销成本 o(log n)？

假设我们最初得到一组 n 个数字。我们需要构建一个支持 Search()、Predecessor() 和 Deletion() 查询的数据结构。

Search 和 Predecessor 应该花费最坏情况 O(log processing n) 时间。删除应该花费平摊的 O(log n) 时间。允许的提前时间为 O(n)。我们最初有 O(n) 空间。但我希望在任何阶段，如果它们是结构中的 m 个数字，则使用的空间应该是 O(m)

这个问题可以使用 RBT 轻松解决，但我想要一个仅使用数组的数据结构。我不想使用数组来实现 RBT，数据结构不应该使用任何受树启发的算法。谁能想到一种这样的数据结构？

我试图在数据结构上的 n 个操作序列中找到每个操作的摊销成本，其中如果 i 是 3 的精确幂，则第 i 个操作成本 i，否则为 1

谁能解释我如何解决这个问题

我找到了 O(6)，我不知道它是正确的还是错误的。

我在研究要求考虑执行一系列 n 操作的数据结构时遇到了这个问题。如果第 k 个操作的成本为 k，如果它是完全平方，则成本为 1，那么操作的总成本是多少，每个操作的摊销成本是多少。

我想出一个求和公式有点困难，该公式提供了一个完美平方的定义，我可以在其中看到总和的结果。有什么想法/建议吗？

我正在学习算法分析，我遇到了一个问题。

我做了什么

我编写了一个程序，它生成 30 棵随机大小的二叉树，其中每棵树的每个节点都有随机值。现在为了使用摊销分析，我（根据需要）为树的每个节点分配了一个等级，如下所示

" 如果一个节点的等级是 r，那么它的左孩子的等级是 r -1，它的右孩子的等级是 r + 1。"

现在要定义每个节点的摊销复杂度，我将以下等式转换为 C++ 代码

"ai = ti + Φ(Si) − Φ(Si−1)" ，其中 Si−1 是 D 在第 i 次调用开始之前的状态，而 Si 是 D 刚刚完成之后的状态。

还剩下什么

我必须将实验结果与摊销分析的估计进行比较。

我在这部分是盲目的，不知道该怎么做。任何擅长它的人，或者只是把我推向正确的方向。我在其他任何地方都找不到帮助。

的复杂性std::map::erase(iterator)摊销为O(1)（例如，请参见此处）。虽然标准库没有规定实现，但事实上这意味着红黑树所需的重新平衡操作的数量是摊销的O(1)。事实上，关于红黑树的维基百科条目似乎证实了这一点：

恢复红黑属性需要少量（O(log n) 或摊销的 O(1)）颜色变化（在实践中非常快）并且不超过三个树旋转（两个用于插入）。

但似乎没有链接（我在其他地方找不到它）。

由于旋转次数是恒定的，因此摊销取决于节点根路径上所需的重新着色次数。虽然平衡树中的大多数节点都朝向树的底部（因此平均路径是对数的），但它显然是摊销的O(1)，这是令人惊讶和有趣的。如何证明摊余不变成本？

如果我有 n 个单节点树和 m 个查找集合操作（​​注意：没有联合，假设之前已经完成了联合）并且只使用路径压缩，这真的需要 O(m) 时间吗？我一直试图证明这一点，但似乎并非如此。由于联合没有按等级使用联合，因此查找集可能需要 O(n) 时间。但是仍然有可能在 O(m) 时间内完成 m 查找集吗？

设 x 为空数组的大小。如果数组变满，将创建一个长度为 k > x 的新数组。旧数组的内容将被复制到新数组中，新元素也将被存储。

• 在 k 步中创建一个长度为 k 的数组
• 复制一个元素需要固定的时间。

问题：如何选择 k 使得每个插入操作都有摊销的常数时间，并且插入 n 个元素需要 Θ(n)？通过摊销分析证明您的选择会导致每次插入操作的摊销时间恒定。

我的直觉说 k = 2*n 是个好主意，但我不知道如何证明它。我认为我根本不了解摊销分析。有什么建议么？

如果二进制计数器花费 O(2^i) 时间来更改第 i 位的值，那么 n 次增量操作的总成本的上限是多少？