資料結構中的陣列加倍

有時我們使用動態記憶體分配建立陣列。如果陣列是使用動態記憶體分配技術分配的，我們可以透過執行一些操作來將陣列的大小加倍。

假設初始陣列大小為 5。

陣列

陣列加倍後，大小為 -

要將大小為 n 的陣列 arr（arr[0…n-1]）的大小加倍。首先，我們必須建立一個大小為 m 的新陣列。然後將 arr 中的 n 個元素複製到新陣列中。最後，更改 arr 的值以指向新陣列。

建立大小為 m 的陣列需要 θ(m) 的時間。這是因為它將用一些預設值初始化。然後，它需要額外的 θ(n) 時間才能從舊陣列複製到新陣列。因此，該操作需要 θ(m + n) 的時間。此操作發生在陣列已滿時。通常，m 值與 2n 相同。因此，複雜度為 θ(2n + n) = θ(3n)，相當於 θ(n)。但此操作被認為是昂貴的。但是，此操作在後續 n 次迭代中進行攤銷，則每次迭代僅增加 θ(1) 的時間。因此，我們可以理解，陣列大小以常數因子增加不會對漸近複雜度產生不利影響。

Arnab Chakraborty

更新於: 2020年8月10日

2K+ 閱讀量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習