在C++中，通过引用访问向量元素是否会降低空间复杂度？

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;
}

我的问题是，考虑到空间复杂度由辅助空间和输入空间组成，说我的算法的空间复杂度是线性的（因为输入大小可能会变化）是否正确？还是说空间复杂度是恒定的，因为输入已经存在于内存中（只是被引用了），除了我的临时的 n 变量？

Answer 1

由于你只是在向量上使用引用，所以你不需要更多的内存。你唯一要写的是 grade += (5-n)，像任何 int (或数字类型)，这发生在变量当前被寻址的地方--在本例中是向量本身。

据我所知，你在这里多分配了一个int，而且没有使用其他 "辅助 "空间。也许还有一个用于引用的空间(像指针一样)，不过我不确定，因为实现中可能使用了 grades+int_offset 来直接访问变量，而不需要额外的指针。

Answer 2

空间复杂度是恒定的吗，因为输入已经存在于内存中（只是简单的引用），除了我的临时n变量，不需要额外的空间？

是的。

时间复杂度是O(grade.size())，空间复杂度是O(1)。

但是，如果你去掉引用，用记号描述的渐进时间复杂度为O(1)。O 或者更准确地说， θ 这里不会改变。因为这只会影响访问每个元素所花费的时间常数。

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