请问这段C++程序的时间复杂度是O(n)还是O(n²)？

先看你提供的这段C++代码：

#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)，其中n是所有子vector里元素的总个数，这里就是9个元素。

为什么不是O(n²)？你担心的insert确实会涉及元素拷贝，但要算总开销：

• 首先，insert在vector末尾添加元素时，只有当vector容量不够时才会触发扩容。而vector的扩容策略是指数级增长（比如每次容量翻倍），这意味着整个过程中扩容导致的元素拷贝总次数是O(n)——比如从容量1到2到4到8到16，每次拷贝的元素数加起来是1+2+4+8=15，接近2n，属于线性开销。
• 其次，每个元素只会被从子vector拷贝到最终vector一次，这部分的总操作次数就是n次，也是线性的。

两者加起来，总时间复杂度还是O(n)。如果想进一步优化，可以提前计算所有子vector的元素总数，调用flattened.reserve(total_count)避免扩容开销，但即使不这么做，整体复杂度依然是线性的。

内容的提问来源于stack exchange，提问作者MWaleed Malik