demande de tutoriel

**deubelte** · 26/12/2006, 14h55

y a t il un tutoriel qui explique comment ca marche la fonction logarithmique?

**deubelte** · 26/12/2006, 14h56

pardon, je ne voulait pas dire "la fonction logarithmique", je voulais dire: la fonction "std::set" (qui permet de faire des recherches logarithmiques).

**Matthieu Brucher** · 26/12/2006, 15h13

Pourquoi un tutoriel sur une fonction bien documentée ?

**deubelte** · 26/12/2006, 15h50

un tutoriel
.... ou un cours.
mais bon, j'ai trouvé (sur ce site).

**Laurent Gomila** · 26/12/2006, 20h24

?

**loufoque** · 27/12/2006, 02h56

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.

demande de tutoriel

C++

Discussions similaires

Partager

Partager