问题标签 [amortized-analysis]

我猜你已经知道，如果数组中的所有条目都从 0 开始，并且在每一步我们将计数器增加 1（通过翻转 0 和 1），那么 k 增量的摊销成本为 O(k)。

但是，如果数组以 n 开头会发生什么？我认为 k 增量的复杂性现在可能是 O(log(n) + k)，因为在开始时 1 的最大数量是 log(n)。

有什么建议么 ？

提前致谢

如何计算二叉搜索树中n个插入序列的摊销成本？输入序列是随机的，每次插入都会增加一个节点。

我目前正在阅读摊销分析。我无法完全理解它与我们为计算算法的平均或最坏情况行为而执行的正常分析有何不同。有人可以用排序或其他东西的例子来解释吗？

我正在寻找对事物如何运作的理解，而不仅仅是答案。尽管答案是，我给出了我所知道的，但我不太确定，而且文本中没有太多关于这种分析的内容。

我很清楚这不是你应该如何实现堆栈的方式，但这是我们给出的场景。

A部分

插入包含 N 个整数（表示堆栈）的（未排序）数组 a 的插槽 a[0] 的最坏情况、平均情况和最佳情况运行时间是多少？给出 theta 范围。

B部分

如果每次插入都发生在 a[0] 处，则将 N 个整数插入一个初始为空的数组 a（代表一个堆栈）的摊销运行时间是多少？给出一个紧密的 O 界并解释你的答案。

讲师很清楚我们正在对 a[0] 进行所有插入，并且没有从这个“堆栈”中删除。

我的分析是这样的

假设：a.length >> N

最好的情况是 Theta(1)，它发生在我们插入一个空的“堆栈”时。

最坏的情况是 Theta(N)，因为作为插入过程的一部分，我们必须移动 N-1 个元素以在 a[0] 处腾出空间。

平均情况也是 Theta(N)，因为无论如何，我们总是要移动 N-1 个元素。

摊销案例

每个插入成本（N-1），我们有 N 个元素，所以我们使用：

摊销成本将是 N^2 / N = O(N)

我遇到的问题是这看起来很容易。我错过了什么，还是我几乎已经死了？

有人可以用外行的术语解释摊销的复杂性吗？我一直很难在网上找到一个精确的定义，我不知道它与算法分析有什么关系。任何有用的东西，即使是外部引用的，都会受到高度赞赏。

我不完全确定摊销复杂性意味着什么。采用平衡二叉搜索树数据结构（例如红黑树）。正常搜索的成本自然是 log(N)，其中 N 是节点数。但是按升序排列的 m 次搜索序列的摊销复杂度是多少。它只是log（N）/m吗？

命题。在 Stack 的大小调整数组实现中，从空数据结构开始的任何操作序列的平均数组访问次数在最坏的情况下是恒定的。

证明草图：对于导致数组增长的每个 push()（例如从大小 N 到大小 2N），考虑N/2 - 1最近导致堆栈大小增长到 k 的 push() 操作，对于 k 从N/2 + 2 to N. 平均 4N 次数组访问以通过 N/2 次数组访问（每次推送一次）来增长数组，我们得到每个操作的平均 9 次数组访问成本。证明任何 M 操作序列使用的数组访问次数与 M 成正比更加复杂。（算法第 4 版第 1.4 章）

我不完全理解证明草图。请帮助我理解这一点。

I am solving a problem from codeforces. According to the editorial, the complexity of the following code should be O(n).

Here, height[i] is the height of i-th hill and r[i] is the position of the first right hill which is higher than height[i], and height[0] is the always greatest among other values of height array.

My question is, how we can guarantee the complexity of the code to be O(n) although the inner while loop's being?

In the inner while loop, the code updates r[i] values until height[i] > height[r[i]]. and the number of the updates depends on height array. For example, the number of updates of the height array sorted by non-decreasing order will be different from that of the height array sorted by non-increasing order. (in both cases, the we will sort the array except height[0], because height[0] should be always maximum in this problem).

And Is there any method to analyze an algorithm which varies on input data like this? amortized analysis will be one of answers?

PS. I would like to clarify my question more, We are to set the array r[] in the loop. And what about this? if the array height = {5,4,1,2,3} and i=1, (r[2]=3, r[3]=4 because 2 is the first value which is greater than 1, and 3 is the first value which is greater than 2) we are to compare 4 with 1, and because 4>1, we keep trying to compare 4 and 2(=height[r[2]]), 4 with 3(=height[r[3]]). In this case we have to compare 4 times to set r[1]. The number of comparison is differ from when height = {5,1,2,3,4}. Can we still guarantee the complexity of the code to be O(n)? If I miss something, Please let me know. Thank you.

我有一个我无法回答的问题：设计一个支持以下特性的数据结构：

将插入第一个空插槽

访问索引为 i 的对象将在 O(1) 时间内完成

不需要支持提取

目标是将未使用的内存量和插入的复杂性降至最低。

证明对于 K 数量的未使用内存，在摊销分析中插入的复杂性是 O(n/k)。

有人有想法吗？

In ArrayList the add operation is amortized operation. So while reading StringBuffer it came to my mind why the StringBuffer is not amortized. Suppose I use append operation on a string buffer object then it should be able to add those many no of characters in it's underlying array implementation. But instead I found in source code that we have

in append operation of string buffer. So my question is can't the StringBuffer be amortized so it can give us less that O(N) complexity?