ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Алгоритмы поиска данных Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем ОСНОВЫ ПРОГРАММИРОВАНИЯ

Задача поиска в структурах данных (search problem) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 Поиск необходимой информации в списке – одна из фундаментальных задач теоретического программирования. Дано: фиксированная последовательность a = a 1, a 2, a 3, …, a n и "ключ" x искомого элемента. Необходимо: определить, входит ли элемент с ключем x в последовательность a и, если входит, индекс элемента key(a i ) = x. Пример: Входные данные:a = 5, 3, 8, 9, 4, x = 9. Выходные данные:элемент x найден, индекс i = 4.

Алгоритм последовательного поиска © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» x = x xx xxx xxxx xxxxx i = 1 i = 2 i = 3 i = 4 i = 5 i = 6

Алгоритм последовательного поиска (псевдокод) 4 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» x xx xxx xxxx xxxxx i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 Алгоритм не предъявляет никаких требований к последовательности, в которой производится поиск. LINEAR_SEARCH(a, x) 1i 1 2 while i n и a i x do 3 i i if i > n then i 0 5 return i x = 11

Алгоритм последовательного поиска (худший случай) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» xxxxxxxxxx Поиск последнего элемента xxxxxxxxxxx Поиск несуществующего элемента Для того, чтобы гарантировать нахождение значения в последовательности необходимо просмотреть все ее элементы, не пропуская ни одного. Это значит, что в худшем случае потребуется выполнить n сравнений, где n – количество элементов в последовательности. Таким образом вычислительная сложность алгоритма последовательного поиска в наихудшем случае – O(n).

Алгоритм последовательного поиска (худший случай) (2) 6 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» LINEAR_SEARCH(a, x)ВремяКол-во 1i 1c1c1 1 2while i n иc2c2 n a i x do c3c3 n 4 i i + 1c4c4 n 5 if i > n then i 0c5c5 1 6 return ic6c6 1 T п(худш) (n) = c 1 + c 2 (n + 1) + c 3n + c 4n + c 5 + c 6 = O(n)

Алгоритм последовательного поиска (средний случай) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 7 Возможно два средних случая: 1.Поиск всегда завершается успешно, то есть искомый элемент всегда присутствует в последовательности a. В данном случае считается, вероятность появления каждого элемента последовательности на входе алгоритма одинакова. 2.Поиск может окончиться неудачей. В этом случае возможно два подхода к анализу: 2.1 Вероятность появления отсутствующего в a элемента равна вероятности появления одного из присутствующих элементов (дополнительное событие) [Дж. Макконнел, с.76] 2.2 Существует некоторый диапазон R значений, каждое из которых равновероятно, при этом последовательность состоит из некоторых элементов этого диапазона.

2.1 Поиск может окончиться неудачей. Вероятность появления отсутствующего в a элемента равна вероятности появления одного из присутствующих элементов (дополнительное событие) [Дж. Макконнел, с.76] Анализ среднего случая (вариант 2.1) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» – 1 шаг 7– 2 шага... x – n шагов

Анализ среднего случая (вариант 2.2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Поиск может окончиться неудачей. Считать, что существует некоторый диапазон R > n значений, каждое из которых равновероятно, при этом последовательность состоит из некоторых элементов этого диапазона , 9, 12, 13, 15, 16, 7, 10, 1, 5, 11, 3, 8, 14, 4, 2, 17, 18, 19, 20 n = 11 R = 20 Вероятность появления на входе алгоритма любого из R чисел – 1/R Вероятность появления на входе алгоритма любого из R чисел – 1/R

Анализ среднего случая (вариант 2.2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 10 На вход алгоритма будут равновероятно подаваться числа из диапазона R. Вероятность появления каждого из R чисел – 1/R. Для чисел x a (их количество – n), сложность в среднем составляет (1/R)S(x), где S(x) – количество шагов, которое необходимо для поиска x в a. Для чисел y a (их количество – (R – n)), сложность равна n

Анализ среднего случая (сопоставление вариантов 2.1 и 2.2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 11 В формуле (2) возьмем R = n + 1, что соответствует предположениям (1) : (1)(2)

Анализ среднего случая (вариант 2.2, различные диапазоны R) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Пусть R существенно больше n и стремится к 2. Пусть R = f(n) = n 2

Алгоритм поиска с барьером 13 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» BARRIER_SEARCH(a, x) 1i 1 2a n+1 x // !!! 3 while i n и a i x do 4 i i if i > n then i 0 6 return i xxxxx x= xxxxxxxxxxx x= 20

xxxxxxxxxx Алгоритм поиска с барьером (худший случай) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 14 Поиск последнего элемента Поиск несуществующего элемента Для того, чтобы гарантировать нахождение значения в последовательности необходимо просмотреть все ее элементы, не пропуская ни одного. Это значит, что в худшем случае потребуется выполнить (n+1) сравнений, где n – количество элементов в последовательности. Таким образом вычислительная сложность алгоритма последовательного поиска в наихудшем случае – O(n) xxxxxxxxxxx

Алгоритм поиска с барьером (худший случай) (2) 15 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» BARRIER_SEARCH(a, x)ВремяКол-во 1i 1c1c1 1 2a n+1 x c while a i x do c'2c'2 n i i + 1c3c3 n 5 if i > n then i 0c4c4 1 6 return ic5c5 1 T б(худш) (n) = c 1 + c' 2 (n + 1) + c 3n + c 4 + c 5 = O(n)

Алгоритм поиска с барьером (средний случай) 16 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Рассуждения при определении вычислительной сложности алгоритма поиска с барьером в среднем аналогичны рассуждениям, приведенным выше для алгоритма последовательного поиска.

Задача поиска в упорядоченной последовательности 17 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Дано: фиксированная последовательность a = a 1, a 2, a 3, …, a n, a 1 a 2 a 3 … a n и "ключ" x искомого элемента. Необходимо: определить, входит ли элемент x в последовательность a и, если входит, индекс элемента a i = x. Пример: Входные данные:a = 3, 4, 5, 8, 9, x = 9 Выходные данные:элемент x найден, индекс i = 4

Поиск c барьером в упорядоченной последовательности 18 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» BARRIER_SORTED(a, x) 1i 1 2a n+1 x 3 while a i < x do 4 i i if a i x или i > n then i 0 6 return i xxxxxxxx x= 11 x= xxxxxxx

Алгоритм поиска с барьером в упорядоченной последовательности (худший случай) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 19 Поиск последнего элемента Поиск несуществующего элемента, который больше последнего Поведение алгоритма поиска с барьером в худшем случае одинаково как для упорядоченной, так и для неупорядоченной последовательностей и составляет O(n+1) xxxxxxxxхх xxxxxxxxxxx

Алгоритм поиска с барьером в упорядоченной последовательности (средний случай) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 20 Возможно два средних случая: 1.Поиск всегда завершается успешно, то есть искомый элемент всегда присутствует в последовательности a. В данном случае считается, вероятность появления каждого элемента последовательности на входе алгоритма одинакова. В данном случае средняя вычислительная сложность не отличается от алгоритма последовательного поиска: 2.Поиск может окончиться неудачей. Существует некоторый диапазон R значений, каждое из которых равновероятно, при этом последовательность состоит из некоторых элементов этого диапазона.

Алгоритм поиска с барьером в упорядоченной последовательности (средний случай) (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 21 a1a1 a2a2 anan... R R / (n+1) a1a1 anan... a2a2 a1a1 a2a2 anan 3. Точки сосредоточены в конце диапазона R 2. Точки равномерно распределены по диапазону R 1. Точки сосредоточены в начале диапазона R Рассмотрим 3 частных случая распределения элементов последовательности a по диапазону допустимых значений R

Алгоритм поиска с барьером в упорядоченной последовательности (средний случай) (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 22 a1a1 a2a2 anan... R 1. Точки сосредоточены в начале диапазона R

Алгоритм поиска с барьером в упорядоченной последовательности (средний случай) (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» a1a1 a2a2 anan 3. Точки сосредоточены в конце диапазона R

Алгоритм поиска с барьером в упорядоченной последовательности (средний случай) (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Точки равномерно распределены по диапазону R R / (n+1) a1a1 anan... a2a2 1 2 n n + 1

Сравнение алгоритмов поиска © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Последовательный поиск 2. Поиск с барьером в отсортированной последовательности 1) Точки сосредоточены в начале диапазона R 2) Точки равномерно распределены по диапазону R 3) Точки сосредоточены в конце диапазона R

Бинарный поиск © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» В рассматриваемом диапазоне [l; u] ([1; 12]) центральный элемент с номером i = l + [(u – l)/2] сравнивается с x. Если a i = x, то поиск завершен успешно, иначе, если l = u, то поиск завершен неудачно. Иначе, если a i x) – продолжить поиск для диапазона [l; i – 1]. Искомый элемент x = xxxxxx l = 1, u = 12, 1+[(12-1)/2] = 6 l = 7, u = 12, 7+[(12-7)/2] = xxxxxxxxxx l = 7, u = 8, 7+[(8-7)/2] = 7

Бинарного поиск (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Искомый элемент x = xxxxxx l = 1, u = 12, 1+[(12-1)/2] = 6 l = 7, u = 12, 7+[(12-7)/2] = xxxxxxxxxx l = 7, u = 8, 7+[(9-7)/2] = xxxxxxxxxxx l = 8, u = 8, 7+[(8-8)/2] = 8 l = u, a l x

Бинарного поиск (3) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Искомый элемент x = xxxxxx l = 1, u = 12, 1+[(12-1)/2] = 6 l = 7, u = 12, 7+[(12-7)/2] = xxxxxxxxxx l = 7, u = 9, 7+[(9-7)/2] = xxxxxxxxxxx l = 7, u = 7, 7+[(7-7)/2] = 7 l = u, a l x Самостоятельно: поиск 4, 15. Самостоятельно: поиск 4, 15.

Алгоритм бинарного поиска 29 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» BINARY_SEARCH(a, x) 1l 1, u n 2do 3 i l + [ (u – l)/2 ] 4 if x < a i then u i – 1 5 else x > a i then l i while (l u и a i x) 7 if l u then i 0 8 return i

Дерево сравнений бинарного алгоритма 30 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» х х – Реальный узел, хранит индекс элемента последовательности – Псевдоузел, соответствует неудачному поиску х х

Количество шагов бинарного алгоритма 31 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» элементаЧисло шагов 61 3,92 1,4,7,113 элементаЧисло шагов 2,5,8,10,124 не вх.3 или 4

Бинарные деревья 32 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Бинарное дерево представляет собой структуру, в которой каждый узел (вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева называется корневым (или корнем) и является единственным узлом без родителя. Узлы, не имеющие потомков называются листьями. Бинарное дерево с N узлами имеет не менее log 2 N+1 уровней (при максимальной упаковке узлов), где x – округление в меньшую сторону. Например, у дерева, изображенного на рисунке N=15, а количество уровней – log = 3,9+1 = 4,9 = 4.

Полное бинарное дерево 33 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» В полном бинарном дереве с j уровнями все листья расположены на уровне j, а у каждого узла на уровнях c 1 по (j – 1) в точности два непосредственных потомка. Полные деревьяНеполные деревья

Свойства полных бинарных деревьев 34 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Рассмотрим свойства полных деревьев: 1.Сбалансированное дерево с N узлами имеет log 2 N+1 уровней. 2.Количество элементов в полном дереве из k уровней: 2 k – 1. 3.Количество Nkэлементов на k-м уровне (разность полных дер.): lev(k) = (2 k – 1) – (2 k–1 – 1) = 2 k – 2 k–1 = 22 k–1 – 2 k–1 = 2 k–1

Особенности деревьев поиска 35 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Дерево поиска, состоящее из k уровней, отличается по структуре от полного дерева такой же высоты только последним уровнем. При этом поддереву, состоящему из реальных узлов (круглой формы), не достает ((2 log 2 N+1 – 1) – N) узлов до полного дерева с k = log 2 N+1 уровнями

Анализ алгоритма бинарного поиска (худший случай) 36 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Как и для последовательных алгоритмов, худшим является случай поиска несуществующего элемента. Для этого требуется пройти (k – 1) или k уровней, при k = log 2 n+1. При достаточно больших n трудоемкость алгоритма составляет: T бин(худш) = O(log 2 n)

Анализ алгоритма бинарного поиска (средний случай) 37 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Возможно два средних случая: 1.Поиск всегда завершается успешно, то есть искомый элемент всегда присутствует в последовательности a. В данном случае считается, вероятность появления каждого элемента последовательности на входе алгоритма одинакова. 2.Поиск может окончиться неудачей. Существует некоторый диапазон R значений, каждое из которых равновероятно, при этом последовательность состоит из некоторых элементов этого диапазона.

Анализ алгоритма бинарного поиска (средний случай, вариант 1) 38 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» При анализе среднего случая ограничимся полными бинарными деревьями, т.е. n = 2 k – 1. Вероятность поиска каждого из элементов последовательности a – 1/N. При рассмотрении свойств полных деревьев было показано, что на k-м уровне полного дерева располагается 2 k–1 элементов. Также ранее было показано, что для поиска корневого элемента требуется один шаг, для поиска элементов перовго уровня – два шага, для второго – 3 и т.д. Найдем общее количество шагов:

Анализ алгоритма бинарного поиска (средний случай, вариант 1) (2) 39 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ»

Анализ алгоритма бинарного поиска (средний случай, вариант 2) 40 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Поиск может окончиться неудачей. Существует некоторый диапазон R значений, каждое из которых равновероятно, при этом последовательность состоит из некоторых элементов этого диапазона. Вероятность поиска x a – n/R, вероятность поиска y a – (R – n)/R. В последнем случае требуется k = log 2 n+1 шагов. Тогда среднее количество шагов определяется по формуле:

Анализ алгоритма бинарного поиска (средний случай, вариант 2) (2) 41 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Аналогично варианту 1

Сравнение алгоритмов: бинарный поиск и поиск с барьером 42 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 1. Поиск с барьером в отсортированной последовательности 1) Точки сосредоточены в начале диапазона R 2) Точки равномерно распределены по диапазону R 3) Точки сосредоточены в конце диапазона R 2. Бинарный поиск