通过引用访问向量元素是否会降低 C++ 中的 space 复杂性？

Question

我有一个简单的 C++ 算法来处理向量中的元素。我通过引用将向量传递给我的函数，并使用这样的 foreach 循环通过引用访问向量的元素：

vector<int>& gradingStudents(vector<int>& grades) {
    for(int& grade : grades) {
        if (grade > 37) {
            int n = grade % 5;
            if (n >= 3)
                grade += (5 - n);
        }
    }
    return grades;
}

我的问题是，考虑到 space 复杂度由辅助 space 和输入 space 组成，说我的算法的 space 复杂度是线性的是否正确（由于输入大小，可能会有所不同）？或者 space 复杂性常数是因为输入已经存在于内存中（它只是被引用）并且不需要额外的 space 除了我的临时 n 变量？

Answer 1

由于您仅使用与向量相关的引用，因此不需要更多内存。您唯一的写入是 grade += (5-n)，并且像任何 int（或数字类型）一样，这发生在变量当前寻址的地方 - 在这种情况下是向量本身。

据我所知，您在这里分配了一个额外的 int，没有使用其他 "auxiliary" space。也许是另一个参考（如指针），但我不确定，因为实现可能使用 grades+int_offset 直接访问变量而无需额外的指针。

Answer 2

is the space complexity constant because the input already exists in memory (it's simply referenced) and no extra space is needed except for my temporary n variable?

是的。

时间复杂度为O(grade.size())，space复杂度为O(1)。

但是，如果您删除引用，用符号 O 或更准确地说 θ 描述的渐近时间复杂度不会在此处改变。因为那只会影响访问每个元素所花费的时间常数。

另外，复制一个int不会花太多时间，它应该和基于范围的for中没有引用的版本几乎一样的速度（甚至更快，因为通常也实现了引用通过指针）。

通过引用访问向量元素是否会降低 C++ 中的 space 复杂性？

Does accessing vector elements by reference reduce space complexity in C++?

c++

algorithm

vector

space-complexity