簡單Algo的時間複雜度

Question

我想弄清下面的代碼的運行時間。

如果add和trimToSize都是O（n），塊的內部將以2N時間運行，然後由於循環需要N次，整個程序將以N *（2N）時間運行。 。O（n^2）？

ArrayList a = new ArrayList(); 

for (int i = 0; i< N; i++){ 
    a.add(i); 
    a.trimToSize(); 
} 

Answer 1

你是對的，它會是O（n^2）。所述for循環執行N次，並像你說，add和trimToSize取O（n）的時間，所以這將是：

N *（N + N）= N *（2N）= 2 * N^2

但是對於大O符號，常數因子2並不重要，因爲n^2是函數的主要部分。因此，它是O（n^2）。

Answer 2

是的。除了必須增加內部存儲陣列的情況外，ArrayList#add通常是O（1）。

如果你想優化你的代碼，這樣做如下：

ArrayList a = new ArrayList(N); // reserve space for N elements 

for (int i = 0; i < N; i++) { 
    a.add(i); // O(1) 
} 

// no need for trimToSize 

這現在只有爲O（n）！