使用常量引用的目标索引查找函数空间复杂度是否为O(n)？

你的判断完全正确，这个函数的空间复杂度确实是O(n)，具体原因如下：

• 入参const vector<string> &num_vector采用引用传递，不会复制原vector的任何元素，仅通过内存引用访问数据，这部分没有额外空间开销。
• 返回的occ向量用于存储匹配元素的索引，最坏场景下（输入vector里所有元素都和目标x一致），occ的长度会等于输入vector的规模n，这部分的空间开销是线性的O(n)。
• 补充说明：入参string x是值传递，会复制目标字符串，这部分空间开销是O(k)（k为字符串x的长度），但在复杂度分析中，我们优先关注和输入核心规模n相关的主导项，所以整体空间复杂度仍为O(n)。

附上你的代码：

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

内容的提问来源于stack exchange，提问作者Sameer