Complexité O(log l)

Bonjour !

vous savez que Si une arbre binaire de recherche est équilibré, la recherche d’un mot prend un temps O(log n)
(où n est le nombre total de mots dans le dictionnaire par exemple).

La question est comment pourrait-on améliorer ce temps pour avoir une complexité de O(log l), où l est la longueur du mot que l’on cherche ?

Que pouvez-vous imaginer comme structure qui obtienne cette complexité ?

Bonjour,

un arbre N-aire avec N le nombre de lettres de l'alphabet utilisé ?
Ce qui en terme de complexité revient à peu près à ce que font les tables de hashages.

Citation:

---

Envoyé par scorpion60

vous savez que Si une arbre binaire de recherche est équilibré, la recherche d’un mot prend un temps O(log n)
(où n est le nombre total de mots dans le dictionnaire par exemple).

La question est comment pourrait-on améliorer ce temps pour avoir une complexité de O(log l), où l est la longueur du mot que l’on cherche ?

---

C'est évidement impossible... Pour être sûr d'avoir trouvé ton mot, il faut bien sûr que tu le parcours au moins une fois complètement. Et ça ça prend... O(l). Donc tu ne peux pas aller en dessous.