问题标签 [amortized-analysis]

事实证明，斐波那契堆很难理解——尽管 CLRS 已经做出了很好的尝试来让它理解它是如何工作的。但有些问题我真的不清楚：

• 为什么要选择像 t + 2m 这样的势函数？原因是什么？
• 节点标记背后的原因是什么 - 我看到将节点放在根列表等中很有用，但你为什么要提出这样的方案？

谢谢！

我无法使我的标题非常具有描述性，抱歉！

对于每个支持某些摊销运行时间的操作的数据结构，在最坏的情况下，另一个支持相同运行时间的相同操作的数据结构是这样吗？我也对迭代的、短暂的数据结构和功能性的数据结构感兴趣。

我敢肯定，这个问题以前一定有人问过。我似乎找不到正确的搜索关键字（在 Google、SO、TCS 中）。我正在{是，否，打开}中寻找引用的答案。

我编写了一个算法来计算整数数组（例如 123、132、213、231、312,323）的下一个字典排列。我认为代码不是必需的，但我将其包含在下面。

我想我已经适当地确定了 O(n) 的最坏情况时间成本，其中 n 是数组中的元素数。但是，我理解如果您使用“摊销成本”，您会发现时间成本可以准确地显示为平均情况下的 O(1)。

问题：

我想学习“会计方法”以将其显示为 O(1)，但我很难理解如何将成本应用于每个操作。记账方法：链接：Accounting_Method_Explained

想法：

我曾考虑应用更改某个位置的价值的成本，或将成本应用到掉期。但这真的没有多大意义。

} // 结束 getNext

骑自行车的人可以在风中以每小时 24 公里的速度行驶，但在逆风中只能以每小时 12 公里的速度行驶。假设骑自行车的人在同一点开始和结束。

骑手的旅行摊销率是多少？

我不明白答案是如何得出的，我已经阅读了我的讲义，但这有点令人困惑。

谢谢

它与渐近分析有何不同？你什么时候使用它，为什么？

我读过一些似乎写得很好的文章，比如：

• http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

• http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

但我仍然没有完全理解这些概念。

那么，任何人都可以为我简化它吗？

我有一组 n 个连续操作，每个操作都以 O(1) 摊销复杂度运行。我可以说整个集合以 O(n) 最坏情况时间复杂度运行吗？我该如何证明呢？

任何人都知道Java HashMap中keySet的摊销分析是什么？ O(1)?

是否遍历它们O(n)？

这种结构对于实时应用程序是必要的——例如用户界面。（用户不关心单击按钮需要 0.1 秒还是 0.2 秒，但他们确实关心第 100 次单击是否会强制执行出色的惰性计算并需要 10 秒才能继续。）

我正在阅读冈崎的论文纯功能数据结构，他描述了一种有趣的通用方法，用于将具有摊销边界的惰性数据结构转换为每个操作都具有相同的最坏情况边界的结构。这个想法是分配计算，以便在每次更新时强制执行一些未评估的 thunk。

我想知道，在 Haskell 中是否有任何标准集合（Map、Set等）的实现？

容器包装说

每个操作的声明成本要么是最坏情况，要么是摊销的，但即使结构是共享的，它仍然有效。

因此不能保证单个操作的最坏情况界限。有严格的变体，例如Data.Map.Strict，但它们的键和值是严格的：

键和值参数被评估为 WHNF；键和值在存储到映射之前会被评估为 WHNF。

它的结构没有（可能的）严格性。

I'm trying to find the amortized cost per operation in a sequence of n operations on a data structure in which the ith operation costs i if i is an exact power of 2, and 1 otherwise.

I think I need to find a way to express the sum of the costs up to a number n, but I'm stuck. I can see that the special, more expensive i values are occurring father and farther apart:

i = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20...

So, it looks like I have no numbers between the first and second powers of 2, then one number, then 3, then 7. When I looked at this a while, I (correct me if this is off) found that the number of non-powers of 2 between the jth and kth powers of 2 is 2^(j-1) - 1.

But how can I tie this all together into a summation? I can kind of see something over the js combined with the number of actual powers of 2 themselves, but I'm having trouble uniting it all into a single concept.

假设我们有一个二进制计数器，它支持两种操作：将所有位递增和重置为零。如果单个位的修改或检查需要 Theta(1) 时间，那么如何将计数器实现为位数组，以便初始零计数器上的任何递增和复位操作序列都需要 O(n) 时间？

通过聚合分析，并考虑到并非所有位每次都必须翻转的事实，我能够看到只允许递增的计数器需要 O(n) 时间进行 n 次操作。但我坚持如何实现增量重置计数器。据我所知，翻转就是翻转，没有什么能比平常更快地神奇地使 1111 变为 0000。但是，我确实注意到，通过增量操作，我们不会经常遇到超级昂贵的全 1 情况。

我想真正的问题是，实际上是否有一种策略可以使用重置实用程序来实现高效的计数器，或者我只是想证明它会变成一个只有增量操作的计数器？我唯一的提示是“保留指向高位 1 的指针”，这似乎暗示了前者。