如何获得渐近运行时间？

Question

我不知道如何获得精确的渐近复杂度，因为以下问题要求我解决。

这里是问题：

我从 class 中学到的一切是，如果存在 "for loop" 运行 N 次，或者递归调用 "recursive method" N 次，那么任何一个都是 O(N)。这几乎是我所知道的所有基础知识。

问题1）关于"N(N+1)/2"的答案，和"O(N(N+1)/2)"一样吗？

此外，答案是 followng "On iteration i, both add and trimToSize require that i array elements be copied to a new array."，我认为它是这样说的，因为它同时调用了 "list.add()" 和 "list.trimToSize()" N 次。

从我的角度来看，这看起来更像是 O(N)... 因为它使用 "list.add()" 添加了 N 次元素，并且还通过 "list.trimToSize()" 对元素进行了 N 次数组复制。因此，N + N <= 2N 所以 O(N) 其中见证 C=2 和 k=1，而不是 O(N(N+1)/2)。然而，我的回答是错误的。因此，

问题2）我只是不知道如何得到N(N+1)/2如答案所说

如能解答，万分感谢！

Answer 1

From my perspective, this looks more like just O(N)... because since it adds ith element N times using "list.add()" and also array-copies element N times through "list.trimToSize()". Thus, N + N <= 2N so O(N) where witness C=2 and k=1, not O(N(N+1)/2).

However, my answer is wrong.

是的。是的。

您将对 trimToSize 的每次调用都视为固定成本。那是不正确的。如果您查看 trimToSize 的作用，您会发现 每次调用 都将所有元素（到目前为止）复制到一个新数组。这不是固定成本

• 在第一次调用 trimToSize 时，数组长度为 1，因此您复制了 1 个元素。
• 在第二次调用 trimToSize 时，数组长度为 2，因此您复制了 2 个元素。
• ...
• 在第 N 次调用 trimToSize 时，数组长度为 N，因此您复制了 N 个元素。

将所有这些相加，所有 trimToSize 次通话您将获得 N(N+1)/2。

（事实上，考虑到代码使用 ArrayList 的方式，每次调用 add 时，都需要重新分配列表的后备数组。所以相同计算也适用于此。)

---

^{请注意 O(N(N+1)/2) 与 O(N^2) 的复杂性相同 class。你可以从第一原理证明这一点。）}