set s; s.insert(1); s.insert(2); ... s.insert(n);
Je me demande combien de temps cela prend à la s.find(k)
où 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.