Complexity and Big-O

假設項目具有足夠的未使用空間而不需要重新調整大小，以下兩種算法的最壞情況時間複雜度是多少？我最初的猜測是A會運行得更慢，因爲它必須將每個元素都移到索引[0]上添加新元素。我認爲在最壞的情況下B是O（N^2），但我不確定。Complexity and Big-O

for (int i = 0; i < N; i++) 
     items.add(0, new Integer(i));

和B.

for (int i = 0; i < N; i++) 
     items.add(new Integer(i));

這真的取決於用來存儲項目的基礎數據結構。如果你使用一個鏈表，插入和A一樣需要一個固定的時間，例如O（1），而如果你使用了一個數組，那麼它將是O（n），因爲你必須將每個元素向左移動1個位置，新項目。因此，如果使用鏈表，則循環將具有複雜度O（n），如果使用數組，則循環爲O（n^2）。

對於B，目前還不清楚你想如何實現add函數，因此沒有什麼可以說它的複雜性。當您使用鏈表，數組或平衡樹時，複雜度會有所不同。

2013-02-13 05:41:50

items是一個ArrayList 。但是爲什麼不是A O（N^2或N^3），因爲它必須將n（n-1）/ 2 => n^2個項目移位n次。 – user1874239 2013-02-13 05:47:32

A確實是O（N或N^2），因爲每個插入需要O（1）或O（N）。我應該清楚地說明這一點。 n^2項目是什麼意思？根據循環A，您只能進行N次插入，因此您有最多N個項目。 – 2013-02-13 06:25:59

，但在A循環結束時，一旦你完全通過它，你將不得不移動n（n-1）/ 2個數字，因爲每次你將新數字加到列表的前面（使用arrayList）而不是在B中，你將它添加到結尾 – user1874239 2013-02-13 15:00:41

回答