Стр. 69 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
67
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
A=(A+
∆
)
mod
m;
}
<неуспех>
Очевидно, что успешный поиск всегда короче неуспешного и
t
включения
=
=
t
неуспеш
.
поиска
.
Если
m
n
=
α
, - коэффициент заполнения таблицы. Если
m
достаточно
велико, то число сравнений для метода двойного совпадения составляет:
C
включ
=
C
безуспеш. поиска
=
α1
1
−
;
C
успеш. поиска
=
)
α1
1 ln(
α
1
−
.
Независимо от
m
, если
m
достаточно велико
α
C
включ.
C
безуспеш. поиска
C
успеш. поиска
0.25
1.33
1.15
0.5
2
1.39
0.75
4
1.85
0.9
10
2.56
0.95
20
3.15
Для метода линейной расстановки
C
включ
=
C
безуспеш поиска
=
))
α1
1 ( 1(
2
1
2
−
+
,
C
успеш поиска
=
)
α1
1 1(
2
1
−
+
.
Независимо от
m
, если
m
достаточно велико
α
C
включ.
C
безуспеш. поиска
C
успеш. поиска
0.5
2.5
1.5
0.75
8.5
2.5
