c++ - vector push_back 的空间复杂度

Question

我的代码首先创建了一个 vector ( vector B)。然后，我的代码循环遍历程序中的不同 vector ( vector A)，并将该索引添加到 vector B 的后面。

我的想法是，由于我们正在遍历 n 个元素，所以时间复杂度在 O(n^2) 的情况下会更糟，因为如果 vector b 变得太大，我们可能需要创建一个全新的数组。 O(n) 的平均时间，因为推回通常是常数。

现在对于空间复杂度，因为我们已经创建了空间来容纳 n 个元素，所以它是 O(N)。但是，如果我们的 vector 太大，我们可能需要创建一个全新的 O(N) 大小的 vector 。那么我们的空间是 O(2n) 还是 O(n + m)(m 是新数组的大小)。

谢谢!

Answer 1

关于时间复杂度:

单次推回的最坏情况是线性的(除非内存是预先保留的，在这种情况下，只要大小不超过保留大小，最坏情况就是恒定的)。平均情况不变。

不管内存是否被预留，N 次推回总数的最坏情况和平均情况都是线性的。

---

So would our space be O(2n) which is just O(n) or would it be O(n + m) (m being the size of the new array).

这实际上并不重要。新大小是旧大小的常数倍数 (c)，所以 O(n + m) -> O(n + (n * c)) -> O ((c + 1) * n) -> O(n)。因此，无论哪种方式，复杂性都是相同的。