std::count的复杂性

Question

我在一个在线代码测验网站上，这个网站有一个复杂度限制，即代码的时间和内存复杂度都不应超过 O(N)，其中 N 是向量 A 的大小。我的代码完整如下：

int foo(int X, const std::vector<int> &A) {
    auto N = A.size();
    auto total_hit = std::count(A.cbegin(), A.cend(), X);
    auto K = N - total_hit;
    if (K < 0 || K >= N){
        return -1;
    }
    return K;
}

我得到了一个超出时间复杂度的结果。除了他们搞错了，还有其他可能吗？

- Humam Helfawi

---

这是完整的代码吗？还是你有未显示的代码？ - gongzhitaao

完整的代码...我不需要编写主函数。 - Humam Helfawi

这个在线编程测验的确切信息/问题是什么？你能提供一个链接吗？ - Vadim Key

@VadimKey很遗憾，协议规定我不应以任何方式传播它。 - Humam Helfawi

- Jarod42

Answer 1

根据引用：

复杂度：谓词的最后一次和第一次比较/应用的确切数量

他们是错误的！

而C++也同意：

复杂度：在第一个和最后一个元素之间是线性的：每个元素只比较一次。

---

当然，std::cbegin()，std::cend()和std::vector::size()的复杂度是恒定的。

---

如果我是你，我会联系网站，并将此问题链接给他们。

- gsamaras