可調整大小的陣列和分期​​運行時間

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）