Que signifie «données non pathologiques»?

J'ai suivi un cours d'algorithmes sur Coursera. Le professeur dans la vidéo sur les tables de hachage a déclaré que

Ce qui est vrai, c'est que pour les données non pathologiques, vous obtiendrez des opérations à temps constant dans une table de hachage correctement implémentée.

Que signifie «données non pathologiques»? Pouvez-vous donner quelques exemples?

Les données pathologiques sont censées être des données qui font que les choses tournent mal d'une manière ou d'une autre pour votre calcul prévu. Il peut être qualifié de pathologique lorsqu'il est assez rare dans les utilisations réelles, de sorte que les choses fonctionnent bien la plupart du temps. Cela peut parfois être rendu mathématiquement plus précis (par exemple avec des probabilités), mais l'utilisation du mot pathologique est souvent informelle.

Par exemple, la salade de tomates et le ketchup sont d'excellents aliments, sauf pour les personnes pathologiques, c'est-à-dire les personnes allergiques aux tomates. Il peut même tuer dans certains cas. Mais les personnes allergiques aux tomates sont très rares, de sorte que les plats de tomates sont considérés comme excellents, sauf dans les cas pathologiques.

$O(n^2)$$O(n \lg n)$$O(n \lg n)$$O(\lg n)$$O(n)$ pour le tri par fusion.

$O(n^2)$

Les données pathologiques sont des données qui rendront l'algorithme mauvais. Pour les tables de hachage, les données pathologiques sont des données qui provoquent des collisions. Cela dépend bien sûr de la fonction de hachage utilisée.

Par exemple, si votre fonction de hachage ajoute les caractères ensemble: hash("abcd") = 'a' + 'b' + 'c' + 'd'. Les données pathologiques ressemblent alors à:

{"abcd", "dcba", "cbda", ...}. Toute permutation du "abcd"hachage de la volonté à la même position, vous vous retrouverez donc avec une liste chaînée que vous tentiez d'éviter en premier lieu.

Les données non pathologiques sont des données qui ne sont pas pathologiques.

une autre façon de voir les choses: les clés de hachage sont comme des "bacs" séparés qui contiennent les données. on peut s'attendre / espérer que les données soient réparties également entre tous les bacs, "équilibrées". pour les données non pathologiques, chaque bac contient / contient à peu près la même quantité de données. si les données sont pathologiques (algorithme de hachage de clé wrt), elles "s'empilent" toutes en moins de bacs, et certains bacs en ont beaucoup moins. cela est inefficace car le temps de recherche augmente (et l'efficacité diminue / converge vers celle de la recherche d'une liste non triée) lorsque les bacs sont remplis plus grands. notez que le simple changement de l'algorithme de hachage des clés pourrait transformer les données de «pathologiques» en «non pathologiques» ou vice versa, d'où l'importance de l'algorithme de hachage.

il existe également de nombreux autres algorithmes pour lesquels la distinction "pathologique vs non pathologique" pourrait être appliquée, avec essentiellement les données "pathologiques" rendant l'algorithme plus performant (par exemple, le concept est également utilisé avec des algorithmes de tri). comme vous pouvez le voir, c'est un concept statistique. également pour le même problème, les données «pathologiques» pour un algorithme peuvent ne pas être «pathologiques» pour un autre. etc.