gpt4 book ai didi

c++ - 说到序列, "vector[n].push_back()"总是 O(1) 吗?

转载 作者:行者123 更新时间:2023-11-27 23:36:02 25 4
gpt4 key购买 nike

我用过 vector<int> v[N]很多。
这对我来说是一个非常强大的工具。

我想知道 v[n].push_back()平均花费 O(1)。
我知道当 vector 满了,它需要扩展成 double。
但是 vector 序列不是相互依附的吗?
如果是这样,我认为所有 vector 都需要向左移动,这意味着它的成本超过 O(n)。

总结一下,当涉及到 vector 序列时,就是v[n].push_back()总是 O(1)?
请给我一些帮助:D

最佳答案

它并不总是 O(1) 无论如何。参见 here (强调我的):

Complexity

Constant (amortized time, reallocation may happen).

If a reallocation happens, the reallocation is itself up to linear in the entire size.

所以即使只有一个 vector ,也不能保证它是常数。

But isn't the sequence of vector attached each other? If so, I think all vectors need to be shift which means it costs more than O(1).

这不会影响运行时。数组中的 vector 彼此独立并动态管理自己的存储(并且彼此分开)。数组中的实际 vector 对象始终具有相同的大小。当您修改数组中的对象时,它不会更改对象的大小并移动数组的其余部分。

关于c++ - 说到序列, "vector[n].push_back()"总是 O(1) 吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59155226/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com