Стр. 23 - Основы алгоритмов и структур данных

Содержание

21

ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ

сумма по всем

i

от 1 до

n,

она будет

∑

=

⋅

n

i

i p

1

,

p

i

- вероятность того, что мы

обращаемся именно к

i

-тому ключу. При равновероятном обращении к ключам

p

i

= 1/

n

.

Тогда в среднем

∑ ∑

=

+

= =

n

i

n

i

n i

n

i

n

1

2

1

1 1

.

Затраты на успешный поиск равна О(

2

1

+

n

).

Очевидно, для неуспешного поиска требуется

n

итераций, то есть

быстродействие неуспешного поиска равно О(

n

).

Время неуспешного поиска больше времени успешного поиска

приблизительно в 2 раза.

Пробуем увеличить быстродействие, не меняя алгоритм: чтобы избежать

постоянной проверки

i <= n

, достаточно предварительно записать

z

в конец

таблицы. Тогда цикл всегда будет заканчиваться успехом и останется 1 лишь

раз проверить, не добавленный ли ключ мы нашли.

Алгоритм №2.

x

n+

1

= z

for (i = 1; x

i

≠z;i++);

if i <= n <успех> else <неудача>

Приём с добавлением

z

в конец таблицы возможен только тогда, когда мы

имеем прямой доступ к концу этой таблицы.

Недостатком 1-го и 2-го алгоритмов является особенно низкое

быстродействие при неуспешном поиске.

Улучшим быстродействие для случая <

неудача

>, предполагая, что

<неудача> происходит достаточно часто. Тогда можно предварительно

отсортировать таблицу, то есть сделать табличный порядок линейным,

x

i

< x

i+

1

,

для любых

i

.

Теперь поиск можно прекращать сразу, как встретится ключ равный или

больше искомого.

Удобно в этом случае в конец таблицы записать бесконечность, чтобы

гарантировать выход из цикла.