使用“常量引用变量”的空间复杂度

Question

这是我的代码，用于查找向量列表中目标变量所在的索引。

vector<int> FindOccurences(string x, const vector<string> &num_vector)
{
    
    vector<int> occ;


    for (int i=0;i< num_vector.size() && num_vector.size() != 0  ; i++ )
    {
        if( num_vector[i] == x )
            occ.push_back(i);

    }

    return occ;
}

我想知道函数的空间复杂度是多少。因为我使用的是

const vector<string> &num_vector

，所以不会有任何额外的空间用于这个向量，对吧？因为它只会在声明的地方访问它。但是

occ

向量的大小可以是

n

。因此空间复杂度为 O(n)。

这是正确的吗？

Answer 1

是的，你是对的（假设你指的是最坏情况分析）。
最坏情况下的空间复杂度为 O(n)。

当

num_vector

中的条目的 O(n) 等于

x

时，这将发生，然后

occ

的大小为 O(n)。

例如，如果 0.5 个条目等于

x

（0.5n 在 O(n) 中），这也将是

occ

的大小。