Анализ алгоритма бинарного поиска (средний случай, вариант 1)
При анализе среднего случая ограничимся полными бинарными деревьями, т.е. n = 2k – 1. Вероятность поиска каждого из элементов последовательности a – 1/N.
При рассмотрении свойств полных деревьев было показано, что на k-м уровне полного дерева располагается 2k–1 элементов.
Также ранее было показано, что для поиска корневого элемента требуется один шаг, ля поиска элементов перовго уровня – два шага, для второго – 3 и т.д.
Найдем общее количество шагов:
|
|
|
k |
|
1 |
k |
|
|
||
Tбин1 |
(сp) |
1 i 2i 1 |
|
i 2i |
|
|||||
|
|
|
||||||||
|
|
|
n i 1 |
|
2n i 1 |
|
|
|||
|
N |
|
|
|
|
|
|
1 |
(k 1)2k 1 |
2 |
|
|
|
|
|
|
|
||||
|
i 2i (N 1)2N 1 2 |
|
||||||||
|
2n |
|||||||||
|
i 1 |
|
|
|
|
|
|
|
|
|
41
Анализ алгоритма бинарного поиска (средний случай, вариант 1) (2)
|
|
|
1 |
k |
|
|
|
|
|
|
|
1 |
|
k |
|
|
|
|
|
|
|
|
|
|
||
Tбин1 |
(сp) |
i 2i |
1 |
|
i 2i |
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
n i 1 |
|
|
|
|
|
|
|
2n i 1 |
|
|
|
|
|
|
|
|
|
|
|||||
|
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
(k 1)2k 1 2 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
i 2i (N 1)2N 1 2 |
|
||||||||||||||||||||||||
|
2n |
|||||||||||||||||||||||||
|
i 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k 2k 1 2k 1 2 |
|
|
k 2k 2k 1 |
|
|
n 2k 1 2k n 1 |
|
|
|||||||||||||||||
|
|
|
|
|||||||||||||||||||||||
|
|
|
2n |
|
|
|
|
|
|
|
n |
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
k (n 1) (n 1) 1 |
|
k n k n |
|
|
k |
k |
1 |
||||||||||||||||||
|
|
|
|
|
|
|
n |
|||||||||||||||||||
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
lim |
k |
|
|
lim |
log 2 n |
1 |
0 |
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
n n |
|
|
n |
|
|
|
n |
|
|
|
|
|
|
|
|
|
||||||
42
Анализ алгоритма бинарного поиска (средний случай, вариант 2)
Поиск может окончиться неудачей. Существует некоторый диапазон R значений, каждое из которых равновероятно, при этом последовательность состоит из некоторых элементов этого
диапазона. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вероятность поиска x a |
– n/R, вероятность |
поиска y a – |
|||||||||||||||||
(R – n)/R. В последнем случае требуется k = log2n+1 шагов. |
|
|||||||||||||||||||
|
Тогда среднее количество |
|
определяется по формуле: |
|||||||||||||||||
2 |
k |
2i 1 |
|
|
|
R n |
k |
k 2k 2k 1 |
|
|
R n |
k |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Tбин(сp) i |
R |
|
|
|
R |
|
R |
R |
||||||||||||
|
|
i 1 |
|
|
|
|
|
|
|
|
|
|
||||||||
|
n 2k 1 2k n 1 |
|
|
k (n 1) (n 1) 1 |
|
|
R n |
|
k |
|||||||||||
|
|
|||||||||||||||||||
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
R |
|
|
R |
|
|||
|
kn k n Rk nk |
Rk k n |
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
R |
|
|
|
|
|
|
|
|
R |
|
|
|
|
|
|
|
|
|
43
Анализ алгоритма бинарного поиска (средний случай, вариант 2) (2)
|
|
T 2 |
|
Rk k n |
|
|
||
|
|
|
бин(сp) |
R |
|
|
||
|
|
|
|
|
|
|
||
|
Rk k n |
|
nk k n |
k |
1 |
Аналогично |
||
R n |
R |
|
|
|
n |
k n |
варианту 1 |
|
|
Rk k n |
|
k |
n |
|
|
lim |
|
lim k |
|
|
|
k |
R |
R |
|
||||
R |
R |
|
|
|
||
R n2 |
|
Rk k n |
|
n2k k n |
k |
k |
|
1 |
|
R |
n2 |
n2 |
n |
||||||
|
|
|
|
|
44
Сравнение алгоритмов:
бинарный поиск и поиск с барьером
1.Поиск с барьером в отсортированной последовательности
1)Точки сосредоточены в начале диапазона R
2 |
2R n |
|
(n 1) |
2R n |
n 1 |
|
Tсб (сp) (n 1) |
2R |
lim |
2R |
|
||
|
R |
|
|
|
||
2) Точки равномерно распределены по диапазону R
T 2 |
|
(n 2) |
n 1 |
|
|||
сб (сp) |
2 |
2 |
|
3) Точки сосредоточены в конце диапазона R
2 |
|
n2 |
n |
|
n2 n |
1 |
|
Tсб (сp) 1 |
|
|
lim 1 |
|
|
||
|
|
2R |
|
2R |
|
|
|
2. Бинарный поиск |
|
R |
|
|
|||
|
|
|
|
|
|
|
|
2 |
Rk k n Rk k n |
|
k n |
log 2 n 1 |
|||
Tбин(сp) |
R |
lim |
R |
lim k |
R |
|
|
|
R |
R |
|
|
|||
45
ФИБОНАЧЧИЕВ ПОИСК
Вэтом поиске анализируются элементы, находящиеся в позициях, равных
числам Фибоначчи. Числа Фибоначчи получаются по следующему правилу: последующее число равно сумме двух предыдущих чисел, например:
1 1 2 3 5 8 13 21 34 55 89 …
Пример: Дано исходное множество ключей {3, 5, 8, 9, 11, 14, 15, 19, 21, 22, 28, 33, 35, 37, 42, 45, 48, 52}. Пусть отыскиваемый ключ
равен 42, т.е. К= 42. Последовательное сравнение отыскиваемого ключа
будет проводиться с элементами исходного множества, расположенными в позициях, равных числам Фибоначчи: {1, 2, 3, 5, 8, 13, 21,...}.
Шаг 1. 42 > 3 => отыскиваемый ключ сравнивается с ключом, стоящим в позиции, равной числу Фибоначчи.
Шаг 2. 42 > 5 => сравнение продолжается с ключом, стоящим в позиции,
равной следующему числу Фибоначчи.
Шаг 3. 42 > 8 => сравнение продолжается.
Шаг 4. 42 > 11 => сравнение продолжается.
Шаг 5. 42 > 19 => сравнение продолжается. Шаг 6. 42 > 35 => сравнение продолжается.
Шаг 42 < 52 => найден интервал, в котором находится отыскиваемый ключ, т.е. он может находиться в исходном множестве между 13-й и 18-
й позициями, т.е. {35, 37, 42, 45, 48, 52}.
Внайденном интервале поиск вновь ведется в позициях, равных числам
Фибоначчи.
МЕТОД ХЭШИРОВАНИЕМ
В основе поиска лежит переход от исходного множества к множеству хеш-функций И(к).
Хеш-функция имеет вид И(к) = к mod т, где к — ключ; т — целое число; mod — остаток от целочисленного деления.
Например, пусть дано исходное множество {9, 1, 4, 10, 8, 5}. Определим для него хеш-функцию И(к) = к mod т.
•1) Пусть т = 1, тогда h(k) = {0, |
0, 0, 0}. Множество хеш-функций |
состоит из нулей. |
|
•2) Пусть т = 20, отсюда h(k) = {9, 1,4, 10, 8, 5}. Множество хеш- функций повторяет исходное множество.
•3) Пусть т = 5, отсюда И(к) = {4, 1,4, 0, 3, 0}.
Хеш-функция указывает адрес, по которому следует искать ключ.
Для разных ключей хеш-функция может принимать одинаковые значения, и такая ситуация называется коллизией. Таким образом, поиск хешированием заключается в устранении коллизий методом
цепочек.
Устранение коллизий методом цепочек
Пример 1.
Дано множество ключей {7, 13, 6, 3, 9, 4, 8, 5}. Найти ключ К =27.
Хеш-функция И(к) = К mod т = [ 13/2] = 6 (поскольку 13 - максимальный ключ) h(k) = {1, 1, 0, 3, 3, 4, 2, 5}.
Для устранения коллизий построим таблицу. Попарным сравнением множества хеш-функций
и множества |
исходных |
заполняем |
таблицу |
(устанавливаем |
взаимно |
однозначное |
соответствие (биекцию) между |
|
двумя множествами. При этом хеш-функция указывает адрес, по которому следует отыскивать ключ. Например, если отыскивается ключ К= 27, тогда
h(k) = 27 mod 6 = 3.
Это значит, что ключ К =21 может быть только в строке, где И(к) = 3. Поскольку его там нет, то данный ключ отсутствует в исходном множестве.
h(k)
0
1
2
3
4
5
Цепочка
ключей
6
7, 13
8
3,9
4
5
Пример |
2. Дано множество |
ключей |
{7, |
1, |
||||
8, |
5, |
14, |
9, |
16, |
3, |
4}. |
Найти |
|
ключ К= 14. |
Хеш-функция |
равна h(k) |
= |
|||||
К mod т; т = [16/2] = 8 (поскольку 16 - максимальный ключ).
Следовательно, h(k) = {7, 1, 0, 5, 6, 1, 0, 3, 4}.
Для разрешения коллизий, которые присутствуют во множестве хеш-функций, построим таблицу. При заполнении таблицы установим соответствие исходным
множеством |
и множеством хеш-функций. |
|||
Поиск |
осуществляется |
по |
таблице: К |
|
= 14; |
h(k) |
= 14 mod 8 = |
6. Это значит, |
|
что ключ |
К = 14 может |
быть |
только в |
|
строке со |
значением h(k) = 6. |
|
||
Цепоч
ка
h(k) ключе
й
0 |
8, 16 |
1 1,9
3 3
4 4
5 5
6 14
7 7