Un théoricien qui considère que comparer deux chaînes se fait en O(1), c'est pas un théoricien.
Hasher une chaîne c'est toujours O(l), alors que comparer une chaîne, c'est O(l), au pire. Si tes chaînes commencent pas par les mêmes lettres (ce qui est courant), ta complexité est bien réduite.
Et la dernière fois que j'ai regardé, rééquilibrer un arbre binaire ça coûte moins cher que d'augmenter la taille d'une table de hachage.
Enfin bref, selon le jeu de données, les résultats sont différents. C'est ça, de la bonne théorie. :)
(La pratique, c'est lorsqu'on se tape le cache du CPU, la rotation des disques et l'OS)
[^] # Re: Les vrais théoriciens s'en foutent
Posté par Batchyx . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 2.
Un théoricien qui considère que comparer deux chaînes se fait en O(1), c'est pas un théoricien.
Hasher une chaîne c'est toujours O(l), alors que comparer une chaîne, c'est O(l), au pire. Si tes chaînes commencent pas par les mêmes lettres (ce qui est courant), ta complexité est bien réduite.
Et la dernière fois que j'ai regardé, rééquilibrer un arbre binaire ça coûte moins cher que d'augmenter la taille d'une table de hachage.
Enfin bref, selon le jeu de données, les résultats sont différents. C'est ça, de la bonne théorie. :)
(La pratique, c'est lorsqu'on se tape le cache du CPU, la rotation des disques et l'OS)