Сложность хеш-таблицы - PullRequest
Новая
       11

Сложность хеш-таблицы

1 голос
/ 22 февраля 2012

Я пытаюсь определить лучшие, худшие и средние случаи для хэш-таблицы: Размер хеш-таблицы m, входной размер n.

  1. Поиск имени в хешированной телефонной книге со «средними» данными, где столкновения существуют, но линейное зондирование является разрешением столкновения схема
  2. Нахождение k-го самого большого элемента в хеш-таблице, которая использует линейное зондирование для разрешения коллизий?
  3. Нахождение k-го по величине элемента в хеш-таблице, которая использует отдельную цепочку для разрешения коллизий?

Мои ответы: 1. Лучшее: 1 Худшее: м Среднее: м / 2 2. Лучшее: 1 Худшее: м Среднее: м / 2 3. Наилучшее: 1 Наихудшее: 1 + n Среднее: (1 + 1 + n) / 2 = n?

Я думал, что в любом случае поиск одного конкретного элемента в любом ADT (Tree, Hash, Array) всегда равен 1. Потому что каким-то волшебным образом вы нашли то, что вам нужно в O (1), я также подумал, что Средний случай просто худший + лучший / 2. Это правильно?

Поправь меня, если мое мышление не так.

1 Ответ

0 голосов
/ 12 июня 2015
  1. Худший случай O (n).Это входной размер, поскольку может быть не более n зондов, так как вы не наступите на свободное место до достижения этого значения.Средний регистр и лучший регистр O (1).

Если k-й по величине элемент относится к k-му наибольшему из имеющихся ключей.

Наихудший случай: O (kn) Средний и лучший случай: O (k).

Худший случай: O (kn) Средний и лучший случай: O (k)).

...