將1個元素添加到擴展數組中的最壞情況時間

Question

假設我們有一個擴展數組，當我們嘗試向其中添加某些內容但它已被填充時，它的大小加倍。

根據幻燈片底部"Amortization: Expanding Vectors"加入一個元素的最壞情況時間是2N，而不是N？爲什麼是這樣？

我認爲這將是N，因爲將N個元素複製到新的雙倍大小的陣列需要N次。

例如，說我加入一個元素大小4的滿陣這將是這樣的：

1. 讓大小8（雙4）的新陣列。
2. 將原始數組的所有元素複製到新數組（複製4次）。
3. 將新數組的第五個元素設置爲附加元素（複製1次）。

因此，將複製元素5次，這是N + 1，而不是2N？

Answer 1

將元素添加到擴展數組中需要的操作是O（2N），因爲首先需要檢查整個數組，並使用O（N）檢查空的空間。因爲這是最糟糕的情況，所以不需要創建一個新數組，並使用O（N）將整個內容從第一個數組複製到新數組。兩種操作的結合都是O（2N）。

當你想到數組長度時，長度實際上是爲數組保留的大小，而不是內部元素的數量。這就是爲什麼如果你沒有在任何地方保存元素的數量，你需要遍歷整個數組的空間。我說的是'空白空間'，因爲沒有說明只是添加了元素而且沒有在數組內部刪除。