用於向ArrayList中添加N個項目的Big-O運行時間

假設我將N個項目添加到Java中的ArrayList。這最糟糕的運行時間是什麼？我知道它可能是O（N）來添加一個項目，因爲數組可能需要調整大小。它不會調整N次，因爲我添加了N個項目，甚至N個因子，因爲每次調整大小時，（AFAIK）容量都會以某個因子增加。這意味着某種日誌（N）調整大小。所以它似乎應該是O（N日誌（N））插入N項，但我不完全確定這一點。我正在看的一門舊計算機科學考試的答案爲O（N^2）。我錯過了什麼？用於向ArrayList中添加N個項目的Big-O運行時間

int newCapacity = (oldCapacity * 3)/2 + 1;（from this answer）

來源

2015-05-09 sudo

如果每個調整大小都將陣列容量增加相同的數量，則O（N^2）是成本界限。也許這就是考試問題所要求的。 –

其實，我發現考試題意味着插入任何位置。這包括前面，它需要把所有東西都轉移下來。那是O（N^2）。 – sudo

的dynamic array被充分研究在計算機科學分期時間分析。簡短的答案是，當從空的動態數組開始並添加元素時，總時間爲O（N）。

你是正確的，將單個項目有Ø（ñ）時，必須進行調整大小，而Ø最壞情況下的時間（登錄ñ）調整發生。

但是，當我們加起來這些調整操作，一共是唯一Ø（ñ），這是非常好的。下面是一個例子來說明比例因子是2（而不是ArrayList的比例因子3/2）：

N = 64：調整爲1,2,4,8,16,32,64。總計操作= 127（大約2 N）。

來源

2015-05-09 18:36:08 Nayuki

不應該執行O（N）操作log（N）次導致O（N log（N）），就像添加到TreeMap一樣？我知道將N項添加到一棵平衡樹（而不是真正地細細研究）被認爲是O（N log N）。 – sudo

從技術上說是的，但是N log N是*悲觀*分析。 O（N）是緊密的分析。 – Nayuki

關鍵在於* N *在每個調整大小時都不相同，並將它們相加得到大約2 * N *。 – Nayuki

用於向ArrayList中添加N個項目的Big-O運行時間

回答

相關問題