Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Доказательство. M: Si=0 M CL+iL =Si=0 M-1 CL+iL + CL+ML = CL+ML+1 + CL+ML =

Читайте также:
  1. Доказательство.
  2. Доказательство.
  3. Доказательство.
  4. Доказательство.
  5. Доказательство.
  6. Доказательство.
  7. Доказательство.

M=0: CLL = CL+1L+1

M: Si=0 M CL+iL = Si=0 M-1 CL+iL + CL+ML = CL+ML+1 + CL+ML =

=(L+M)!/((L+1)!M!) + ((L+M)!/(L!M!))= (L+M+1)!/((L+1)!M!)= CL+M+1L+1

¢

Оценим время добавления элемента к хэшированной таблице методом проб в случае, когда в таблице из N записей занято M позиций. Это время, фактически, совпадает с неудачным временем поиска значения в таблице (т.е. поиска элемента, если его в таблице нет).

Если вслед за позицией, на которую указала хэш-функция следует k-1 занятая запись (включая запись, на которую указала хэш-функция), то время вставки есть Q(k) (т.к. для поиска свободной позиции надо будет осуществить k проб). Пусть вероятность того, что начиная с данной позиции следует k-1 занятых позиций, а следующая позиция свободна, равна pk. Тогда, учитывая то, что количество подряд занятых позиций не может превзойти M, среднее время вставки элемента пропорционально

TM = Si=1 M+1 k pk

Вероятность pk равна количеству перестановок оставшихся M-k+1 занятых позиций среди оставшихся N-k записей, деленное на общее число перестановок CNM. Итак

pk= CN-kM-k+1 / CNM

TM = Sk=1 M+1 k pk = Si=1 M k CN-kM-k+1 / CNM =

(учитывая Cnk=Cnn-k)

= Sk=1 M+1 k CN-kN-M-1 / CNM =

(учитывая Si=1 M k pk=1)

= N+1 - Sk=1 M+1 (N + 1- k) CN-kN-M-1 / CNM =

= N+1 - Sk=1 M+1 ((N-k+1)! / ((N-M-1)!(M-k+1)!)) / CNM =

= N+1 - Sk=1 M+1 (N -M) CN-k+1N-M / CNM =

(замена i=M-k+1, k=M-i+1)

= N+1 - Si=0 M (N -M) CN-M+kN-M / CNM = N+1 -(N -M) CN-M+M+1N-M+1 / CNM=

=N+1-(N-M) ((N+1)!/((N-M+1)!M!)) M!(N-M)!/N! =

= N+1 – (N-M)(N+1)/(N-M+1) = (N+1)/(N-M+1)


Оценим теперь время удачного поиска. Легко увидеть, что все операции, производимые для удачного поиска некоторого элемента списка, совпадают с операциями, которые производились для вставки этого элемента в список. Среднее время удачного поиска равно среднему из всех средних времен, затрачиваемых на поиск каждого элемента в списке. Поэтому, среднее время удачного поиска равно среднему из времен вставки элементов, находящихся на данный момент в списке, в список. Т.о., если рассматривать элементы в списке в порядке их поступления в список, то получим, что среднее время удачного поиска равно

TM = 1/(M+1) Si=0 M Ti = 1/(M+1) Si=0 M (N+1)/(N-i+1)=

= 1/(M+1) Si=0 M (N+1)/(N-i+1)= 1/(M+1) Sj=N-M+1 N+1 (N+1)/j£

(N+1)/(M+1)ò t=N-M+1 N+1 1/t dt=(N+1)/(M+1) log((N+1)/(N-M+1))

 

Т.о. если ввести коэффициент заполненности таблицы a=M/N, то верна следующая теорема

Теорема. Среднее время неудачного поиска элемента в таблице, состоящей из N записей, M из которых заполнены

ТM=Q(1/(1-a)), где a=M/N – коэффициент заполненности таблицы.

Среднее время удачого поиска имеет следующую оценку

ТM =Q((1/a) log(1/(1-a)))


Дата добавления: 2015-10-30; просмотров: 132 | Нарушение авторских прав


Читайте в этой же книге: Поиск кратчайшего пути в графе | Добавление элемента | Сбалансированные и идеально сбалансированные бинарные деревья поиска | Добавление элемента в дерево | Разбиение дерева по разбивающему элементу | Добавление элемента в красно-черное дерево | Однопроходное добавление элемента в красно-черное дерево | Удаление элемента из красно-черного дерева | Отступление на тему языка С. Быстрый поиск и сортировка в языке С | Удаление вершины из B-дерева |
<== предыдущая страница | следующая страница ==>
Метод линейных проб| Метод цепочек

mybiblioteka.su - 2015-2024 год. (0.006 сек.)