请参考上述材料的答案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。
有人可以说明一下吗?