Complessità di std :: conteggio

Question

ero in qualche sito codice di quiz on-line in cui v'è una limitazione della complessità che il codice non deve superare i O (N) in termini di tempo e di memoria in cui N è la dimensione del vettore A. Il mio codice era esattamente (Full Code):

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

Ho ottenuto un risultato che ho superato la complessità del tempo. C'è qualche possibilità piuttosto che sbagliare?

Answer 1

Secondo il ref:

Complessità: esattamente last - prime comparazioni/applicazioni del predicato

si sbagliano!

E cplusplus concorda:

Complessità: lineare nella distanza tra il primo e l'ultimo: Confronta volta ogni elemento.

---

Naturalmente, la complessità di std::cbegin(), std::cend() e std::vector::size() è costante.

---

_{Se fossi in te, mi metterei in contatto con il sito, collegandoli a questa domanda.}