Алгоритмы и структуры данных на С++. Аксёнова Е.А - 73 стр.

UptoLike

ВУЗ: 

ПетрГУ | Петрозаводск

Составители: 

Рубрика: 

Глава 6. Поиск
6.1. Последовательный поиск
Задача: пусть задана таблица записей с ключами K
1
, K
2
, ..., K
n
.
Нужно найти в таблице запись с ключом K (или убедиться в его от-
сутствии).
Алгоритм последовательного поиска:
R1: i = 1;
R2: если K
i
= K, то УДАЧА;
R3: i = i + 1;
R4: если i ≤ n, то перейти к шагу R2;
иначе НЕУДАЧА.
Оказывается, что данный алгоритм можно ускорить при помощи
вставки ключа поиска в конец массива ключей.
Быстрый последовательный поиск:
B1: i = 1, K
n+1
= K;
B2: если K
i
= K, то перейти к шагу B4;
B3: i = i + 1; перейти к шагу B2;
B4: если i ≤ n, то УДАЧА;
иначе НЕУДАЧА.
В этом алгоритме быстрее выполняется самый внутренний цикл
за счет того, что не надо выполнять проверку i ≤ n.
Пусть теперь известны вероятности: p
1
, p
2
, . . . , p
n
, где
P
p
i
= 1.
Возникает задача: как расположить ключи, чтобы среднее время по-
иска было минимально. Среднее время вычисляется по формуле T =
C(p
1
·1+p
2
·2+p
3
·3+...+p
i
·i+...+p
n
·n). Очевидно, что эта функция
достигает минимума, если p
1
≥ p
2
≥ ... ≥ p
n
.
                          Глава 6.         Поиск

                  6.1. Последовательный поиск

   Задача: пусть задана таблица записей с ключами K1 , K2 , ..., Kn .
Нужно найти в таблице запись с ключом K (или убедиться в его от-
сутствии).
   Алгоритм последовательного поиска:

     R1:   i = 1;
     R2:   если Ki = K, то УДАЧА;
     R3:   i = i + 1;
     R4:   если i ≤ n, то перейти к шагу R2;
           иначе НЕУДАЧА.
   Оказывается, что данный алгоритм можно ускорить при помощи
вставки ключа поиска в конец массива ключей.
   Быстрый последовательный поиск:

     B1:   i = 1, Kn+1 = K;
     B2:   если Ki = K, то перейти к шагу B4;
     B3:   i = i + 1; перейти к шагу B2;
     B4:   если i ≤ n, то УДАЧА;
            иначе НЕУДАЧА.
    В этом алгоритме быстрее выполняется самый внутренний цикл
за счет того, что не надо выполнять проверку i ≤ n.
                                                                           P
    Пусть теперь известны вероятности: p1 , p2 , . . . , pn , где             pi = 1.
Возникает задача: как расположить ключи, чтобы среднее время по-
иска было минимально. Среднее время вычисляется по формуле T =
C(p1 · 1 + p2 · 2 + p3 · 3 + ... + pi · i + ... + pn · n). Очевидно, что эта функция
достигает минимума, если p1 ≥ p2 ≥ ... ≥ pn .

Страницы