这个程序(c++)的时间复杂度是多少

Question

代码：

#include <iostream>
#include <vector>

template<typename T>
std::vector<T> flatten(std::vector<std::vector<T>> const &vec)
{
std::vector<T> flattened;
for (auto const &v: vec) {
flattened.insert(flattened.end(), v.begin(), v.end());
}
return flattened;
}

int main()
{
std::vector<std::vector<int>> vec {
{ 1, 2, 3 }, { 4, 5 }, { 6, 7, 8, 9 }
};

std::vector<int> flattened = flatten(vec);
for (int &i: flattened) {
std::cout << i << ' ';
}

return 0;
}

上面代码的时间复杂度是O(n(还是O(n^2(？我知道这只是一个for((循环，但在for循环中使用insert((会使其为O(n^2(吗？

Answer 1

O(∑_i=0ⁿm_i(，

其中n是外部向量的大小，m_i为第i个内部向量的大小。

如果外向量的大小和内向量的大小都是O(n(，那就等于O(n²(。