J'essaie de trouver les meilleurs, les pires et les cas moyens pour le tableau de hachage: Taille de la table de hachage m, taille n.
- Rechercher un nom dans un répertoire haché avec des données «moyennes», où les collisions existent, mais le sondage linéaire est la résolution de la collision schème?
- Trouver le k-ème élément dans une table de hachage qui utilise le sondage linéaire pour la résolution des collisions?
- Trouver le k-ème élément le plus important dans une table de hachage utilisant un chaînage séparé pour la résolution des collisions?
Mes réponses: 1. Le meilleur: 1 Le pire: m Moyenne: m / 2 2. Meilleur: 1 Pire: m Moyenne: m / 2 3. Meilleur: 1 Pire: 1 + n Moyenne: (1 + 1 + n) / 2 = n?
Je pensais que toute recherche de cas pour unL'élément particulier de tout ADT (Tree, Hash, Array) est toujours 1. Parce que, d'une manière magique, vous avez trouvé ce dont vous avez besoin en O (1), j'ai également pensé que la casse moyenne est simplement pire / meilleur / 2. Est-ce correct?
Corrigez-moi si ma pensée est fausse.
Réponses:
0 pour la réponse № 1- Le pire des cas, O (n). C’est la taille de l’entrée car au maximum n sondes peuvent être présentes car vous ne pourrez pas vous déplacer sur l’emplacement libre avant d’atteindre cette valeur. Affaire moyenne et meilleure affaire O (1).
Si le kème élément le plus volumineux correspond à la kième clé la plus grande présente.
Plus mauvais cas: O (kn) Moyenne et meilleure: O (k).
Plus mauvais cas: O (kn) Moyenne et meilleure: O (k).