Временная сложность простого 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 * (2N) = 2 * N^2

, но постоянный коэффициент 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)!