複雑::時間とメモリの両方のカウント

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

私は時間の複雑さを超える結果を得ました。彼らが間違っているのではなく、可能性はありますか？ refによると

Answer 1

：

複雑：まさに最後の - 述語の最初の比較/アプリケーション

彼らは間違っています！

そしてcplusplusは同意する：

複雑を：最初と最後の間の距離のリニア：各要素一度に比較します。もちろん

---

、std::cbegin()、std::cend()とstd::vector::size()の複雑さは、定数です。

---

_{私があなただったら、私はこの質問へのリンク、サイトに連絡します。}