y a t il un tutoriel qui explique comment ca marche la fonction logarithmique?
Version imprimable
y a t il un tutoriel qui explique comment ca marche la fonction logarithmique?
pardon, je ne voulait pas dire "la fonction logarithmique", je voulais dire: la fonction "std::set" (qui permet de faire des recherches logarithmiques).
Pourquoi un tutoriel sur une fonction bien documentée ?
un tutoriel
.... ou un cours.
mais bon, j'ai trouvé (sur ce site).
:resolu: ?
T'as pas du comprendre l'histoire de "recherche logarithmique".
La recherche normalement c'est en O(n) (tu parcoures tous les éléments jusqu'à ce que tu trouves celui que tu veux)
Si tes éléments sont triés, tu peux utiliser une recherche par dichotomie, qui est en O(log n).
Si tes éléments sont hachables, tu peux obtenir un index dans un tableau en O(1).
std::set est implémenté comme un arbre binaire, qui maintient donc l'ordre.
La fonction membre find fait donc déjà une recherche dichotomique avec complexité logarithmique.