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.
Faudrais savoir ce que l'on veut mesurer. Si on cherche à mesurer le nombre de comparaison (ce qui est généralement le cas quand on parle des tables de hashage).
De plus dans le cas que tu parle, le hash c'est O(l) et la comparaison c'est O(l/2). Ils font donc partie de la même classe de complexité, c'est peut être une amélioration, mais ça se rapproche plus de la micro-optimisation qu'autre chose.
Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
[^] # Re: Les vrais théoriciens s'en foutent
Posté par barmic . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 4.
Faudrais savoir ce que l'on veut mesurer. Si on cherche à mesurer le nombre de comparaison (ce qui est généralement le cas quand on parle des tables de hashage).
De plus dans le cas que tu parle, le hash c'est O(l) et la comparaison c'est O(l/2). Ils font donc partie de la même classe de complexité, c'est peut être une amélioration, mais ça se rapproche plus de la micro-optimisation qu'autre chose.
Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)