c++ - std::count 的复杂性

Question

我在一些在线代码测验网站上有一个复杂性限制，即代码在时间和内存上都不应超过 O(N)，其中 N 是 vector 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;
}

我得到了超过时间复杂度的结果。有没有可能而不是他们错了？

Answer 1

根据ref :

Complexity: exactly last - first comparisons / applications of the predicate

他们错了!

和cplusplus同意:

Complexity: Linear in the distance between first and last: Compares once each element.

---

当然，std::cbegin()的复杂性, std::cend()和 std::vector::size()是常数。

---

_{如果我是你，我会联系网站，将他们链接到这个问题。}