问题标签 [amortized-analysis]

我们有一个斐波那契数大小的动态数组。假设 F(k) 是数组的当前大小（F(k) 是斐波那契数列的第 k 个数）。我们这里有两个规则： 1）如果在数组中插入一个元素后，数组元素的个数是 F(k-1)，我们创建一个大小为 F(k+1) 的新数组并复制前面的元素到新数组。2）如果从数组中删除一个元素后，数组元素的个数为F(k-3)，我们创建一个大小为F(k-1)的新数组，并将之前的元素复制到新数组中。

起初，数组是空的，大小为 2。我们想要证明对于每个动作序列（插入或删除），每个动作的分摊时间复杂度为 O(1)。

为了解决这个问题，我意识到在两个数组增长动作之间至少有 F(k-1)-F(k-2) 个动作，并且复制元素需要 O(F(k-1)) 时间。此外，在两个数组收缩操作之间至少有 F(k-2)+F(k-3) 次操作，复制元素需要 O(F(k-3)) 时间。你能帮我解决这个问题吗？

我正在阅读有关破解编码面试的摊销时间。作者开始谈论总和，我不明白为什么我们要从右到左求和，以及这如何给我们 2X (X+x/2+...)

“1 + 2 + 4 + 8 + 16 +... +X 的总和是多少？如果你从左到右阅读这个总和，它从 1 开始并加倍直到它到达 X。如果你从右到左阅读，它从 X 开始并减半直到它达到 1。那么 X+x/2+x/4+x/8+...+1 的总和是多少？这大约是 2X。因此，X 插入需要 O( 2X) 时间。每次插入的摊销时间为 O(1)。"

我有一个动态数组，我不断地将项目附加到该数组上。追加是复杂性O(1)。当数组变满时，我想扩大数组并将其复制过来，这就是复杂性O(n)。

现在，假设我在阵列变满时以不同的速度增长阵列。这些费率是：

i) 一些常数 C

ii) n/2

iii) n^2

在每种情况下，摊销运行时间是多少？

我相信我能够解决案件i。摊销运行时间将是操作的总成本除以操作的总数。在这种情况下，总成本为C * O(1) + 1 * O(n)，操作总数为C。因此，摊销运行时间为O(n).

但是，在分析剩下的两个案例时，我有点迷茫。在我看来，操作的总数将分别为n/2 + 1和n^2 + 1，但我不太清楚如何计算操作的总成本。

谁能带领我走上正确的道路？

所以一个常规的二叉堆有一个操作 extract_min 是 O(log(n)) 最坏的时间。假设 extract_min 的摊销成本为 O(1)。设 n 为堆的大小

因此，我们执行了 n 个 extract_min 操作的序列，它最初包含 n 个元素。这是否意味着整个序列将在 O(n) 时间内处理，因为每个操作都是 O(1)？

一个数据结构支持一个操作 foo，这样在最坏的情况下，一系列 n 个操作 foo 需要Θ(n log n)时间来执行。

a) foo 操作的摊销时间是多少？

b) 单个 foo 操作的实际时间可以有多大？

a）首先我假设 foo 是 O(log n) 最坏的情况。因此，摊销成本来自于 foo 讲述其最坏情况的频率。由于我们一无所知，因此摊销介于 O(1) 和 log n 之间

b) O(log n)

它是否正确？在这里争论的正确方法是什么？

是否存在链表允许比使用（偶尔“重建”）向量的摊销时间更低的运行时复杂性的情况？

例如，一个简单的分析表明，在最坏的情况下，push_back链表上的 O(1) 和向量上的 O(n)。但是，如果向量在每次调整大小时都翻倍，则摊销时间push_back也是 O(1)。

是否存在使用向量的摊销时间不能减少到链表的摊销时间的情况？

请参考上述材料的答案2。我可以按照文本直到那一点。当没有插图时，我似乎总是松散概念化，这可能是因为我对数学符号不熟悉。

我了解昂贵操作的成本（堆栈已满时数组加倍）

1 + 2 + 4 + 8 + ... + 2^i 其中 i 是该序列的索引。所以索引 0 = 1、1 = 2、2 = 4 和 3 = 8。

我可以看到昂贵操作的顺序，但我对以下解释感到困惑。

现在，在 n 操作的任何序列中，调整大小的总成本是 1 + 2 + 4 + 8 + ... + 2^i 对于某些 2^i < n （如果所有操作都是推送，那么 2^i 将是2 小于 n 的最大幂）。这个总和最多为 2n - 1。加上插入/删除的额外成本 n，我们得到总成本 < 3n，因此我们每次操作的摊销成本 < 3

没看懂这个解释？

调整大小的总成本是 1 + 2 + 4 + 8 + ... + 2^i 对于某些 2^i < n

对某些人来说意味着什么2^i < n

它是否说操作数 n 将始终大于 2^i？n 代表操作的数量还是数组的长度？

以下是我不遵循的：

如果所有操作都是推送，那么 2^i 将是 2 小于 n 的最大幂。这个总和最多为 2n - 1。

有人可以说明一下吗？

所以情况是这样的，对于 n 位二进制字符串 A[0....n-1] 的增量算法，其中 A[0] 是最低有效位，A[n-1] 是最高有效位，是：

但是在索引 k 处翻转一点的成本是 2^k

我在试图证明这种修改后的二进制增量算法的摊销成本是 O(logn) 时迷失了方向。无论我如何尝试接近，摊销成本似乎仍然很大 O(1)，尽管常数更大。

增量函数的聚合分析。 如果我跟进这个细分并在 sigma 内乘以 2^i，因为翻转第 i 位的成本是 2^i，我得到 n 增量的 nk。这仍然给了我 O(1) 的摊销成本

我不确定我在这里做错了什么。直观地说，它仍然是 O(1) 是有意义的，因为高成本的高位只是抵消了它被翻转的低概率。

假设翻转位 #i^花费2 i；因此，翻转位#0 花费1，翻转位#1 花费2，翻转位#2 花费4，依此类推。

Increment()如果我们调用n次，调用 的摊销成本是多少？

我认为n增量的成本应该是n ·2 ⁰ /2 ⁰  +  n ·2 ¹ /2 ¹  +  n ·2 ² /2 ²  + … + n ·2 ^{n -1} /2 ^{n -1}  =  n ( n -1) =  O ( n ² )。所以每个增量应该是O ( n )，对吧？但是作业要求我证明它是O (log  n )。我在这里做错了什么？

我最近正在阅读 Java 中的 ArrayList。据我了解，当 ArrayList 达到其容量时，它会调用其 resize 方法并创建一个新的底层数组，该数组的大小是原始数组的两倍。由于这种情况，这种方式插入可以被视为 O(n)，但平均而言它仍然是 O(1)。然而，我对它背后的原因感到困惑，特别是增加了两倍的大小。将其增加 3 倍于原始容量会更好吗？