c++ - 引用传递和值传递是否会导致C++程序时间复杂度的变化？

Question

在 Java 中，我从来没有真正担心过参数是否通过引用传递，因为这是不可能的。在 C++ 中，虽然通过值或引用传递参数的两种方式都是可能的，但是通过大 O 符号传递参数的任何一种方式都会对时间复杂度分析产生影响吗？在计算大 O 表示法时，当参数通过引用或值传递时，如何确定差异或变化？我发现有人说是，而其他人说不是，对此有明确的答案吗？

Answer 1

这个问题没有是或否的答案，因为有时将一个转换为另一个可能行不通。

为了解释发生了什么，我针对两个方向举了两个简单的例子。

从按引用传递到按值传递

在这个方向上，答案是肯定的。例如

bool binary_search(std::vector<int> &arr, int key)
{
    return std::binary_search(arr.begin(),arr.end(),key);
}

这是一个vector中的二分查找函数，复杂度是O(log n) 其中n是arr .size().

但是如果我们将其修改为按值传递，例如:

bool binary_search(std::vector<int> arr, int key)
{
    return std::binary_search(arr.begin(),arr.end(),key);
}

复杂度变为 O(n)，因为函数应该复制 arr。

从按值传递到按引用传递

在这个方向上，转换可能行不通。例如

std::vector<bool> batch_search(std::vector<int> arr, std::vector<int> keys)
{
    std::sort(arr.begin(), arr.end());
    std::vector<bool> res;
    for(auto key:keys)
    {
        res.push_back(std::binary_search(arr.begin(),arr.end(),key));
    }
    return res;
}

这是一个批量搜索功能。函数首先对 vector 排序 一个拷贝，然后搜索每个键。复杂度为 O(n log n + m log n)，其中 m 为 keys.size()。

如您所见，函数sort 在使用它之前对arr 进行了排序。因此，直接将 arr 从按引用传递转换为按值传递是行不通的。

转换为按引用传递的一种方法如下:

std::vector<bool> batch_search(std::vector<int> &arr, std::vector<int> keys)
{
    std::vector<int> copy_arr(arr);
    std::sort(copy_arr.begin(), copy_arr.end());
    std::vector<bool> res;
    for(auto key:keys)
    {
        res.push_back(std::binary_search(copy_arr.begin(),copy_arr.end(),key));
    }
    return res;
}

只需复制它，然后对拷贝进行排序，因为您需要的是 vector 的值。或者从某种意义上说，它是通过引用传递来实现按值传递。

或者另一种方式是:

std::vector<bool> batch_search(std::vector<int> &arr, std::vector<int> keys)
{
    std::vector<bool> res;
    for(auto key:keys)
    {
        res.push_back(std::find(arr.begin(),arr.end(),key)!=arr.end());
    }
    return res;
}

这种方式改变了算法，避免了sort，复杂度为O(n*m)。

但是这两种方式都不是直接转换param，而是重写了batch_search。在讨论按引用传递和按值传递时，似乎某些按引用传递实现的功能不能直接转换为按值传递。