Quelle est la complexité temporelle de la méthode find dans un ensemble en c ++?

set s; s.insert(1); s.insert(2); ... s.insert(n); 

Je me demande combien de temps cela prend à la s.find(k)k est un nombre de 1..n? Je suppose que c’est log (n). Est-ce correct?

O (log N) pour rechercher un élément individuel.

§23.1.2 Tableau 69

 expression return note complexity a.find(k) iterator; returns an iterator pointing to an logarithmic const_iterator element with the key equivalent to k, for constant a or a.end() if such an element is not found 

La complexité de std::set::find() étant O(log(n)) signifie simplement qu’il y aura des comparaisons log(n) des objects stockés dans l’ set .

Si la comparaison des 2 éléments de l’ensemble est complexe O(k) , la complexité réelle serait alors O(log(n)∗k) .
Cela peut arriver, par exemple, dans le cas d’un ensemble de chaînes (k serait la longueur de la chaîne la plus longue), car la comparaison de 2 chaînes peut impliquer de comparer la plupart (ou la totalité) de leurs caractères égal)

La documentation dit la même chose:

Complexité

Logarithmique en taille.