C++中vector<vector<int>>调用push_back(vector<int>)的时间复杂度咨询

当你声明vector<vector<int>> matrix并调用matrix.push_back(array)（其中array是vector<int> {1,2,3}）时，时间复杂度是O(n)，n为array中的元素个数，你的第一个猜测是对的，原因如下：

• matrix的元素类型是vector<int>，调用push_back时会把传入的array完整复制一份作为matrix的新元素。复制一个vector<int>的操作需要遍历它的所有元素，逐个复制到新的内存空间，这个过程的时间开销和元素数量n成正比，也就是O(n)。
• 你提到的array.push_back(5)是O(1)（均摊复杂度），这是因为它只需要复制单个int类型元素，单个基础类型的复制是常数时间操作，和容器大小无关，两者的操作对象完全不同——前者复制的是整个容器，后者复制的是单个基础元素。

额外补充：如果使用移动语义，比如调用matrix.push_back(std::move(array))，此时时间复杂度会变成O(1)。因为移动vector不需要复制元素，只是转移它内部管理的内存指针、大小、容量等元数据，这个过程是常数时间。但要注意，执行移动操作后，原来的array会处于“有效但未定义”的状态，不能再正常使用它的元素。

内容的提问来源于stack exchange，提问作者maverick.01