gpt4 book ai didi

c++ - 为什么动态数组必须以几何方式增加其容量以获得 O(1) 分摊 push_back 时间复杂度?

转载 作者:行者123 更新时间:2023-12-03 06:56:23 25 4
gpt4 key购买 nike

我了解到动态数组,如 std::vector,在达到其容量时将其容量加倍,从而使 push_back 操作 O(1) 摊销时间。

但是,为什么首先需要这样做?在 vector 末尾为一个元素分配空间并在那里复制新元素不是已经 O(1) 了吗?

最佳答案

如果你想在数组的末尾分配空间,那只有在该位置的内存可用时才有效。其他东西可能已经存在,或者该内存可能无法使用。所以调整数组大小的方式(一般):

  1. 创建一个新的更大的数组,

  2. 将原数组中的元素复制到更大的数组中,并

  3. 销毁原数组。

如您所见,当您增加数组的大小时,您付出的代价与数组的原始大小成正比。

因此,如果您从具有一个元素的数组开始并添加第二个元素,则必须将第一个元素复制到另一个数组中。如果添加第三个元素,则必须复制其他两个元素。如果添加第四个元素,则必须复制前三个。这样加起来就是 1+2+3...+N,等于 N(N+1)/2,也就是 O(N2)。参见 Arithmetic Progression (Wikipedia)

如果您按几何级数调整数组的大小,您仍然需要每次都复制元素,但您复制它们的次数更少

如果你通过加倍数组来调整大小,那么当你得到一些大小 N 的幂时,N/2 将被复制 0 次,N/4 将被复制一次,N/8 将被复制两次,等等。 0N/2 + 1N/4 + 2N/8 + 3N/16... 的总和在 O(N) 中。参见 Geometric Series (Wikipedia)

您不需要选择倍增,您可以选择其他因素,例如 1.5 倍。选择不同的因子不会改变渐近复杂度,但会改变实际性能。

关于c++ - 为什么动态数组必须以几何方式增加其容量以获得 O(1) 分摊 push_back 时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64734694/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com