Алгоритм последовательного поиска (средний случай)
Возможно два средних случая:
1.Поиск всегда завершается успешно, то есть искомый элемент всегда присутствует в последовательности a. В данном случае считается, вероятность появления каждого элемента последовательности на входе алгоритма одинакова.
2.Поиск может окончиться |
. В этом случае возможно |
два подхода к анализу: |
|
2.1Вероятность появления отсутствующего в a элемента равна вероятности появления одного из присутствующих элементов (дополнительное событие) [Дж. Макконнел, с.76]
2.2Существует некоторый диапазон R значений, каждое из которых равновероятно, при этом последовательность состоит из некоторых элементов этого диапазона.
11
Анализ среднего случая (вариант 2.1)
2.1 Поиск может окончиться неудачей. Вероятность появления отсутствующего в a элемента равна вероятности появления одного из присутствующих элементов (дополнительное событие) [Дж. Макконнел, с.76]
16 
7 
10 
1 
5 
11 
3 
8 
14 
4 
16 – 1 шаг
7 – 2 шага
. . .
x– n шагов
T 1 |
|
p(k) k p(x) n |
1 |
|
|
i n |
|
|
|
||||||||||
|
|
|
n |
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
п(сp) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n 1 |
|
|
n 1 |
|
|
|
|
|||||||
|
|
|
i 1 |
|
|
|
|
|
i 1 |
|
|
|
|
|
|
||||
|
1 (n 1) n |
|
n |
n |
n 1 1 |
n |
1 |
1 |
|
n 2 |
O(n) |
||||||||
|
|
|
|
|
|
|
|
|
|||||||||||
|
n 1 |
2 |
|
n 1 |
n 1 |
||||||||||||||
|
|
|
2 |
n 1 |
|
|
2 |
|
|
2 |
|
||||||||
12
Анализ среднего случая (вариант 2.2)
2.1 Поиск может окончиться неудачей. Считать, что существует некоторый диапазон R > n значений, каждое из которых равновероятно, при этом последовательность состоит из некоторых элементов этого диапазона.
|
|
|
|
R = 20 |
|
|
|
|
|
|||
6, 9, 12, 13, 15, 16, 7, 10, 1, 5, 11, 3, 8, 14, 4, 2, 17, 18, 19, 20 |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
Вероятность |
|
|
|
|
|
|
|
|
|
|
|
|
появления на входе |
|
16 |
7 |
10 |
1 |
5 |
11 |
3 |
8 |
14 |
4 |
2 |
алгоритма |
|
любого из R |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
n = 11 |
|
|
|
|
чисел – 1/R |
|||
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
13 |
|
Анализ среднего случая (вариант 2.2)
На вход алгоритма будут равновероятно подаваться числа из диапазона R. Вероятность появления каждого из R чисел – 1/R.
Для чисел x a (их количество – n), сложность в среднем составляет (1/R)∙S(x), где S(x) – количество шагов, которое необходимо для поиска x в a.
Для чисел y a (их количество (R – n)), сложность равна n
T 2 |
n |
|
p(k) k p(x) n n |
1 |
k |
R n |
n |
||||||||||
|
|
|
|||||||||||||||
|
п(сp) |
|
|
|
|
|
|
|
R |
R |
|||||||
|
|
|
|
i 1 |
|
|
|
|
|
|
i 1 |
||||||
|
1 (n 1) n |
n |
R n |
|
n2 n |
|
Rn n2 |
|
|||||||||
|
R |
|
|
2 |
|
|
R |
2R |
|
|
R |
||||||
|
|
|
|
|
|
|
|
|
|
||||||||
|
2Rn n2 |
n |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
2R |
|
|
|
|
|
|
|
|
|
|
|
|
|
14
Анализ среднего случая (сопоставление вариантов 2.1 и 2.2)
|
Tп1(сp) n 1 |
|
1 |
|
(1) |
|
Tп2(сp) 2Rn n2 n |
(2) |
|||||||
|
|
n 1 |
|
||||||||||||
|
|
2 |
|
|
|
|
|
|
|
|
2R |
|
|||
В формуле (2) возьмем R = n + 1, что соответствует |
|||||||||||||||
предположениям (1) : |
|
|
|
|
|
|
|
|
|
|
|
|
|||
R n 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T 2 |
2(n 1)n n2 n |
|
n2 3n |
|
n2 n |
|
2n |
|
|||||||
|
|
|
|
||||||||||||
п(сp) |
|
2(n 1) |
|
|
|
2(n 1) |
|
|
2(n 1) |
2(n 1) |
|
||||
|
|
|
|
|
|
|
|
||||||||
n(n 1) |
n 1 1 |
n |
1 |
1 |
|
|
|
|
|
|
|
||||
(n 1) |
|
|
|
||||||||||||
2(n 1) |
(n 1) |
2 |
|
|
|
|
|
|
|||||||
15
Анализ среднего случая
(вариант 2.2, различные диапазоны R)
|
|
|
T 2 |
|
|
2Rn n2 |
n |
|
|||
|
|
|
|
|
|
|
|
|
|
||
|
|
|
п(ср) |
|
|
2R |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||
1. Пусть R существенно больше n и стремится к |
|||||||||||
lim |
2Rn n |
2 |
n |
|
|
|
|
n |
n |
2 |
n O(n) |
|
|
|
|
|
|
||||||
2R |
|
|
lim n |
2R |
|
||||||
R |
|
|
|
R |
|
|
|
||||
2. Пусть R = f(n) = n2
2n2n n2 n |
|
2n3 |
n2 |
n |
n |
1 |
|
1 |
O(n) |
2n2 |
|
2n2 |
|
2 |
2n |
||||
|
|
|
|
|
|
16
Алгоритм поиска с барьером
x= 11
x= 20
BARRIER_SEARCH(a, x)
1i ← 1
2an+1 ← x // !!!
3while i ≤ n и ai x do
4i ←
5 if i > n i ← 0
6return i
16 |
7 |
10 |
1 |
5 |
11 |
3 |
8 |
14 |
4 |
2 |
11 |
x |
x |
x |
x |
x |
|
|
|
|
|
|
|
16 |
7 |
10 |
1 |
5 |
11 3 |
8 |
14 |
4 |
2 |
20 |
|
x x x x x x |
x x x x x |
|
|||||||||
17
Алгоритм поиска с барьером (худший случай)
Поиск последнего |
16 |
7 |
10 |
1 |
5 |
11 |
3 |
8 |
14 |
4 |
2 |
2 |
элемента |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
|
|
Поиск несуществующего |
16 |
7 |
10 |
1 |
5 |
11 |
3 |
8 |
14 |
4 |
2 |
20 |
элемента |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
|
Для того, чтобы гарантировать нахождение значения в последовательности необходимо просмотреть все ее элементы, не пропуская ни одного.
Это значит, что в худшем случае потребуется выполнить (n+1) сравнений, где n – количество элементов в последовательности.
Таким образом вычислительная сложность алгоритма последовательного поиска в наихудшем случае – O(n).
18
Алгоритм поиска с барьером (худший случай) (2)
BARRIER_SEARCH(a, x) |
Время |
Кол-во |
|
1 |
i ← 1 |
c1 |
1 |
2 |
an+1 ← x |
c1.1 |
1 |
3 |
while ai x do |
c'2 |
n + 1 |
4 |
i ← i + 1 |
c3 |
n |
5 |
if i > n then i ← 0 |
c4 |
1 |
6 |
return i |
c5 |
1 |
Tб(худш)(n) = c1 + c'2∙(n + 1) + c3∙n + c4 + c5 = O(n)
19
Задача поиска в упорядоченной последовательности
Дано: фиксированная последовательность a = a1, a2, a3, …, an , a1 ≤ a2 ≤ a3 ≤ … ≤ an и "ключ" x искомого элемента.
Необходимо: определить, входит ли элемент x в последовательность a и, если входит, индекс элемента x.
Пример:
Входные данные: a = 3, 4, 5, 8, 9 , x = 9
Выходные данные: элемент x найден, индекс i = 4
20