假设我的输入大小为 n,这 n 个元素被压入一个 vector 。
我最近开始学习空间复杂度,但我有点困惑。所以它查看内存使用情况,但这是动态分配的内存?
vector<int> v;
虽然这没有使用“new”关键字,但我读到一个 vector 实际上是在你推送时动态分配的,所以这是否意味着空间复杂度只是 O(n)?
最佳答案
是的,std::vector
的空间复杂度与其size()
(或者实际上是其capacity()
)成线性关系.请注意,虽然 std::vector
对象本身可以静态或动态分配,但其数据内容始终是动态分配的。 (正如@DyP 在评论中指出的那样,实际分配的方式取决于您为 vector 使用的分配器。但默认分配器使用动态分配)。
关于c++ - 将 n 个元素插入 vector 的空间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20426804/