可调整大小的阵列和分期​​运行时间

Question

“因此，插入N个元素需要O（N）个工作总计。每个插入平均为O（1），尽管在最坏的情况下每个插入需要O（N）个时间。这个引用在破解编码访问中找到。即使关于它的一点小事让我感到厌烦，我也会理解这种说法。在好的日子里，摊销的插入是O（1）。这仅仅意味着，当可调整大小的数组不需要调整大小时，然后插入一些内容就是简单的O（1）。这很清楚。但是，在糟糕的一天，当我们用完空间时，我们需要O（N）来插入那个额外的元素。但是，我不同意上面的说法，它表示在最坏的情况下，有些插入采用O（N）。不应该说，在最坏的情况下，ONE插入采用O（N）。

为了使这个更清楚，下面是我说的一个例子。假设我们有一个可调整大小的数组，但是我们该数组的大小是4。现在让我们说插入5个元素，我们有O（1），O（1），O（1），O（1），但是一旦我们到达最后一个元素，我们将不得不将所有这些家伙复制到一个新的数组中，这个过程会给我们一个O（N）的代价。

有人可以请澄清这一点对我来说。我不明白为什么这本书说，当我们在旧数组中运行空间时，只需要将所有元素复制到一个新数组中时，某些情况下会使用O（N）。

Answer 1

std::vector将保留其所有元素彼此相邻的在内存中快速迭代 - 那是它的事，那是做什么的，这就是为什么大家都喜欢std::vector。通常它会保留比它所包含的元素数量多一点的空间，或者内存恰好是免费的，所以当你在vector的末尾添加一个新元素时，vector会很快将你的新元素推到那里。

但是，当vector没有空间展开时，它不能将其现有元素保留在原来的位置并在其他地方开始新列表 - 所有元素必须在内存中彼此相邻！所以它必须找到一个足够大的内存空间来存储所有元素加上你的新内存，然后将所有现有元素复制到那里，然后将新元素添加到最后。广义上讲，如果需要1个单位时间来添加1个元素，则需要N个单位时间来移动N个元素。如果你添加一个新的元素，那是一个操作。如果添加一个新元素并且需要重新定位1024个现有元素，那就是1025个操作。所以重新分配需要多长时间与矢量的大小成比例，因此O(N)。

Answer 2

让我们将所有插入操作分解为“重”插入操作，这些插入操作的时间与元素数量成正比，而“轻量级”插入操作只需要花费一定的时间来完成。然后，如果你从一个空列表开始，并附加一个附加，你将主要有轻插入，但时不时会有一个沉重的插入。

比方说，为了简单起见，每当空间不足时您将数组的大小加倍，并且您从大小为4的数组开始。然后，第一个大小调整将不得不移动四个元素，第二个将移动八，然后十六，然后三十二，然后六十四，然后128，然后256，等等。

请注意，它不只是一个单一的追加需要很长时间 - 粗略地说，如果你有n总的插入，然后粗略记录它们将是沉重的（它们之间的时间不断增长），而其他大致n-log n将是轻的。

Answer 3

我想你应该像这样理解上面的陈述。

起初。数组的大小只是1，并插入一个元素。现在阵列已满！你必须调整它的大小是前一次的2倍。

接下来，数组大小为2.让此过程继续。您可以很容易地注意到，您必须调整数组大小的那一刻是1,2,4,8,16,32，...，2^r。

我会给你提问。

1. 要调整数组大小的时刻有多少次？
2. 直到N（N> = 0）的总成本增加多少？

第一个答案是floor（lgN）倍。你可以很容易地想出来，我认为。如果你找到第一个答案，那么计算这个N步骤的总成本是第二个答案，这很容易（我不知道如何表达数学符号：<）

1 + 2 + 4 + 8 +16 + ... + 2 ^（floor（lgN））= 2 ^（floor（lgN）+1）-1 => O（n）

为了得到每步的平均成本，成N => 0（1）

我觉得需要的阵列时，要调整大小的参考文献提及最坏的情况是。这个调整的成本是成正比的元素个数是数组，O（N）