Вопрос 40 Таблицы (1006393), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Проблемы работы с hash-таблицами.

1. Сложно работать с отсортированными таблицами.

2. Сложно построить hash-функцию.

Если применяем технику борьбы с коллизиями через списки, то мы будем иметь K/N списков. (Здесь допустимо K>N).

Сложность поиска и вставки в этом случае K/(2N), где K/N - плотность hash-функции ( K/N = α ).

Необязательно

Сложность операции вставки и удаления в среднем по всем возможным порядкам поступления:

ТЕОРЕМА (Хиббард, 1962 г.)

В таблице как ДС, содержащей к элементов, средняя

длина просмотра равна:

- при вставке Р(к) = 2(1/2+ 1/3 + 1/4 + ... + 1/(к+1))

- при поиске, исключении, изменении:

Q(k) = ((k+l)/k)P(k)-l;

Усреднение берется по всем возможным порядкам поступления элементов.

Таблицы прямого доступа. Теорема.

В таблице прямого доступа с одинаковой частотой использования ключей при использовании сцепления для разрешения коллизий, среднее число проб определяется

соотношением

1+α/2

Если используется функция вторичного перемешивания, то число проб равно

(1-α/2)\(1-α)

Характеристики

Список файлов ответов (шпаргалок)