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。

有人可以说明一下吗?

4

1 回答 1

1

n是最大的堆栈大小,此时的固有数组大小是 2 的最小幂2^(i+1)>=n,因此最后一次展开操作需要2^i<n时间。

例如,如果数组达到 size n=11,则最后一次扩展导致从 8 增长到 16 并移动了 8 个项目

关于第二个问题:几何级数之和

1 + 2 + 4 + 8 + ... + 2^i = 2^(i+1) - 1
于 2019-09-19T06:31:54.983 回答