algorithm - 这个关于动态调整数组大小的公式是如何得出的？

Question

我还将此发布到 mathematics.stackexchange 和 theorycomputerscience.stackexchange。但我不确定它是否真的更适合这个论坛。

我正在阅读 Skiena 的“算法设计手册”。

他分析了在动态数组中执行的复制操作的数量。

“假设我们从一个大小为 1 的数组开始，每次空间用完时将其大小从 m 加倍到 2m。这个加倍过程涉及分配一个大小为 2m 的新连续数组，将旧数组的内容复制到新数组的下半部分。明显的浪费是在每次扩展时重新复制旧内容。

Skiena 然后问:

“在总共 n 次插入之后，一个元素可能需要重新复制多少次？”。

然后他给出了一个公式，用于计算 n 次插入的移动总数 M。

他的解释是:

“好吧，当数组在第一、第二、第四、第八……插入后扩展时，第一个插入的元素将被重新复制。这将需要 倍，直到数组有 n 个位置。但是，大多数元素不会遭受太大的剧变。实际上，第 到第 n 个元素将最多移动一次，并且可能根本不需要移动。”

但我真的不明白他是如何从中得出公式的。谁能帮助我了解他是如何达到目标的？主要看不懂的是他为什么要乘通过我。

Answer 1

代表份数。让我们做一个简单的例子。按以下顺序插入

[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

元素 16 使数组加倍(因为它变得大于 2^4)。

让我们计算副本:

15,14,13,12,11,10,9,8 were copied just once (i=1) * (n/2^i)
7,6,5,4               were copied twice (i=2)
3,2                   were copied three times (i=3)
1                     was copied 4 times (i=4)
0                     was copied 5 times (i=5)

因此我想，对于上限，它应该是 ceil(log n) 在总和限制和 ceil(n/2^i) 在总和，但无论如何这应该回答 i 来自哪里的问题。