c++ - 通过值传递和引用传递将大小为 n 的向量传递给另一个函数的时间复杂度是多少？

Question

void fun(vector<int>vec)
{
   some code
}
int main()
{
   int n = 5;
   vector<int>avec(n);
   fun(avec);
}

n通过值传递和引用传递将大小的 Vector 传递给另一个函数的时间复杂度是多少？这段代码只传递一个向量的时间复杂度是多少？

标签： c++pass-by-referencepass-by-value

Answer 1

std::vector通过值将大小传递N给函数显然具有线性复杂性O(n)，因为它涉及复制N对象。通过引用传递具有复杂性O(1)，因为实际上只有 的地址std::vector被传递给函数，而不管其大小。

值得注意的是，std::vector从函数返回 a 的情况有所不同，在这种情况下，按值返回的复杂度为O(1)，因为在这种情况下，编译器要么使用copy elision（如果允许），要么使用移动构造函数。两者都具有O(1)竞争力。