c++ - 将 n 个元素插入 vector 的空间复杂度

Question

假设我的输入大小为 n，这 n 个元素被压入一个 vector 。

我最近开始学习空间复杂度，但我有点困惑。所以它查看内存使用情况，但这是动态分配的内存？

vector<int> v; 

虽然这没有使用“new”关键字，但我读到一个 vector 实际上是在你推送时动态分配的，所以这是否意味着空间复杂度只是 O(n)？

Answer 1

是的，std::vector 的空间复杂度与其size()(或者实际上是其capacity())成线性关系.请注意，虽然 std::vector 对象本身可以静态或动态分配，但其数据内容始终是动态分配的。 (正如@DyP 在评论中指出的那样，实际分配的方式取决于您为 vector 使用的分配器。但默认分配器使用动态分配)。