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

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

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

Answer 2

你是对的，这将是 O(n^2)。for循环执行 N 次，就像你说的那样，花费addO trimToSize(n) 时间，所以它是：

N * (N + N) = N * (2N) = 2 * N^2

但是常数因子 2 对 big-O 表示法并不重要，因为 n^2 是函数的主要部分。因此，它是 O(n^2)。