“因此，插入N个元素总共需要O（N）个工作。每个插入平均为O（1），尽管在最坏的情况下，某些插入也需要O（N）时间。” 此报价可在“破解编码面试”中找到。我有点理解这句话，尽管有一点点让我讨厌。摊销插入时间为O（1）。这只是意味着，当可调整大小的数组不需要调整大小时，只需插入O（1）即可。很清楚 但是，在糟糕的一天，当我们空间不足时，我们需要O（N）来插入额外的元素。但是，当最坏的情况下某些插入需要O（N）时，我不同意上面的说法。应该说，在最坏的情况下，一次插入会占用O（N）。
为了更清楚地说明这一点，这是我所说的例子。
假设我们有一个可调整大小的数组，但该数组的大小为4。现在我们说要插入5个元素，我们将拥有O（1），O（1），O（1），O（1），但是一旦我们到最后一个元素，我们将不得不将所有这些家伙复制到一个新数组中，并且此过程将使我们付出O（N）的代价。
有人可以帮我澄清一下吗？我不明白为什么这本书说某些情况下如果只需要将所有元素都复制到一个新数组中，而当我们在旧数组中运行空间不足时，某些情况下就需要O（N）。
我认为您最好像这样理解上面的声明。
首先。数组大小仅为1.，然后将其插入一个元素。现在阵列已满！您必须将其调整为上一个的2倍。
接下来，数组大小为2。让此过程继续进行。您可以很容易地注意到，必须调整数组大小的时刻是1、2、4、8、16、32，…，2 ^ r。
我会给你问题。
第一个答案是场数（lgN）。我想您可以轻松解决。如果找到第一个答案，则计算这N个步骤的总成本（第二个答案）非常简单。（我不知道如何表达数学符号：<）
1 + 2 + 4 + 8 + 16 + … + 2 ^（floor（lgN））= 2 ^（floor（lgN）+1）-1 => O（n）
要获得每个步骤的平均成本，请将总成本除以N => O（1）
我认为参考文献提到的最坏情况是何时需要调整数组的大小。重新调整的成本与数组中元素的数量O（N）成正比
