问题标签 [amortized-analysis]

我需要一个数据结构来存储 {1, . . . , n}（n 最初给出）并且仅支持以下操作：

• 最初：n 给定，S = {1, . . . , n} 开头。

• delete(i)：从S 中删除i。如果i 不在S 中，则无效。

• pred(i)：返回 i 的 S 中的前任。这意味着 max{j ∈ S | j < i}，S 中严格小于 i 的最大元素。如果没有，则返回 0。参数 i 保证在 {1, . . . , n}，但可能在也可能不在 S 中。

例如，如果 n = 7 且 S = {1, 3, 6, 7}，则 pred(1) 返回 0， pred(2) 和 pred(3) 返回 1。

我需要弄清楚：

• 表示 S 的数据结构
• 初始化算法（O(n) 时间）
• 删除算法（O(α(n)) 摊销时间）
• pred (O(α(n)) 摊销时间的算法)

将不胜感激任何帮助（我不需要代码 - 只是算法）。

我在概念上难以理解插入和获取操作在 Java 的 Hashmap（简化为哈希表）中的分摊运行时间为 O(1) 的事实。请注意，在我的示例中，表是在最大容量下创建的，这意味着它只需要扩展一次，当满足 75% 的负载因子时。也永远不会在无效目标上调用 Get。

摊销运行时间通过 O（总成本）/操作计数计算。

对于插入，将一个元素添加到对应于哈希表中特定槽的桶中。由于总是将最新值添加到存储桶的末尾，因此该值是：

• 总成本 = 找到存储桶 + 存储桶末尾的位置，所有 O(1) 时间
• 操作数 = 找到桶 + 放在桶尾
• 因此，Amortized Running Time = (find bucket + place at bucket end)/(find bucket + place at the end), 或者 O(1)

唯一让我感到困惑的方面是添加的元素是否将表格置于其负载因子之上，并调整其大小。Java 将在这里执行哪些步骤，为什么它仍然是 O(1) 摊销运行时间？

对于 get，查找存储桶的时间是恒定的，查找匹配可能需要 1 次操作（目标是存储桶中的第一个值）到 n 次操作（所有条目都在同一个存储桶中，目标位于底部） ）。在这种情况下：

• 总成本 = 找到桶 + 在桶中找到目标的步数，都是 1 个时间单位
• 操作数 = 找到桶 + 在桶中找到目标的步骤数
• 因此，摊销运行时间=（找到桶+在桶中找到目标的步数）/（找到桶+在桶中找到目标的步数），或O（1）

这是我将摊销思维过程应用于这些操作的尝试，但由于我对这个概念还很陌生，我不确定我的逻辑是否正确，并希望得到一些关于 a) 我是否的反馈m 对或 b) 我哪里出错了。任何帮助表示赞赏。

我正在阅读Cracking the Coding Interview，在Big O一章中，有关于Amortized Time的解释。此处使用了需要增长的诸如 ArrayList 之类的经典示例。当一个数组需要增长时，O(N)假设它必须将 N 个元素复制到新数组中，插入将需要时间。这可以。

我不明白的是，由于数组的容量增加了一倍，为什么每次插入的摊销时间会O(1)根据我的理解，无论何时插入数组，它总是一个O(N)操作。摊销时间有何不同？我确定文字是正确的，我只是不理解O(1)摊销时间的概念。

假设我们使用链表表示来表示每个集合，其中每个节点有 3 个字段，即值、下一个指针和指向集合代表的指针。我们为每个集合维护一个索引对象（或代表），其中包含 3 个字段头、尾和计数（集合中元素的计数）。

对于集合的并集，我们需要为每个元素创建一个新集合，然后对它们进行并集。

n 个元素的每个创建操作都需要 O(1) 时间，因此总计 = O(n)。

现在在联合过程中，我们以这样一种方式组合元素，将较低计数的集合附加到较高计数的集合。因此，n 个集合的并集时间复杂度为 O(n)。

总时间复杂度 =O(n) + O(n) /2n = O(1)。

所以根据我的说法，联合操作的时间复杂度应该是 O(1)，但在任何地方都写成 O(n)。为什么会这样？

我正在学习如何分析算法，我发现了“摊销时间”的符号。我发现了一些预定义的估计，例如：

- 在排序数组中的平均插入时间为：O(n)

从排序数组中删除的摊销时间为：O(1)

谁能给我详细解释一下，拜托！

我如何进行摊销分析并证明后继函数（在中序算法中找到下一个元素的函数）平均为 O(1)？假设后继函数对找到的最后一个元素进行操作。甚至是 O(1) 吗？是 O(log n) 吗？

我需要为平衡 bst 中的后继函数的摊销运行时间提供一个案例。我知道如果从最低的叶子开始，然后到“最大”节点是序列，那么平均运行时间是 O(1)，因为 T(n)/n => O(n)/n = > O(1)

但我不确定当序列不是最长的序列时会发生什么。我很乐意在这方面得到帮助。

我了解对算法进行不同复杂性分析案例的机制，但已经给出了一些场景，并被问到我将针对每种案例使用哪种类型的分析。

分析的类型是“最坏情况”、“平均情况”、“摊销”。

当然，为了确保算法尽可能高效，我们总是会选择使用“最坏情况”吗？

我意识到这是主观的，但使用每种分析方法肯定都有优点吗？

这是我在最近的一次工作面试中遇到的 4 个场景，除了关于飞行员的场景之外，我无法决定其中的任何一个。

一家公司发明了一种新的网络搜索引擎，并希望分析它返回一组常见搜索查询结果的速度有多快。

一名飞行员驾驶飞机，他在控制杆上的输入通过软件计算转换为机翼表面涂层。飞机的稳定性取决于快速反应；我们要分析飞机是否安全。

如果以前未排序，则在第一次进行查询时对数据库进行排序。我们想分析使用这个数据库系统执行多个连续查询需要多长时间。

托管天气预报算法的云计算公司，需要保证在 4 小时内根据压力和其他观测数据计算下一次全国每日预报。

外循环取决于 q。但我不决定 B 的复杂性？

c 的值随每个关键字而变化。我认为这也取决于 c 值。

那么，A的复杂度是多少？

我经常阅读算法教科书 Cormen、Liserson、Rivest 和 Stein。

其中一个有趣的章节是摊销分析。在选择势函数时，二进制计数器是一个困难的例子。我想知道如果计数器是 3 的幂和一些系数（例如 x1*1 + x2*3 + x3*9 +...），该怎么办。

在这种情况下如何确定势函数？