java - 简单算法的时间复杂度

Question

我试图找出下面代码的运行时间。

如果 add 和 trimToSize 都是 O(n)， block 内部将运行 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

是的。但是 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) 了!