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

M=0: C_L^L = C_L+1^L+1

M: S_i=0 ^M C_L+i^L = S_i=0 ^M-1 C_L+i^L + C_L+M^L = C_L+M^L+1 + C_L+M^L =

=(L+M)!/((L+1)!M!) + ((L+M)!/(L!M!))= (L+M+1)!/((L+1)!M!)= C_L+M+1^L+1

¢

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

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

T_M^’ = S_i=1 ^M+1 k p_k

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

p_k= C_N-k^M-k+1 / C_N^M

T_M^’ = S_k=1 ^M+1 k p_k = S_i=1 ^M k C_N-k^M-k+1 / C_N^M =

(учитывая C_n^k=C_n^n-k)

= S_k=1 ^M+1 k C_N-k^N-M-1 / C_N^M =

(учитывая S_i=1 ^M k p_k=1)

= N+1 - S_k=1 ^M+1 (N + 1- k) C_N-k^N-M-1 / C_N^M =

= N+1 - S_k=1 ^M+1 ((N-k+1)! / ((N-M-1)!(M-k+1)!)) / C_N^M =

= N+1 - S_k=1 ^M+1 (N -M) C_N-k+1^N-M / C_N^M =

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

= N+1 - S_i=0 ^M (N -M) C_N-M+k^N-M / C_N^M = N+1 -(N -M) C_N-M+M+1^N-M+1 / C_N^M=

=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)

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

T_M = 1/(M+1) S_i=0 ^M T_i^’ = 1/(M+1) S_i=0 ^M (N+1)/(N-i+1)=

= 1/(M+1) S_i=0 ^M (N+1)/(N-i+1)= 1/(M+1) S_j=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