3.2.3. Задачи поиска

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

Задача поиска является фундаментальной в алгоритмах на дискретных структурах. Задачи сортировки и поиска на практике «идут» «рука об руку». Удивительно, что, накладывая незначительные ограничения на структуру исходных данных, можно получить множество разнообразных стратегий поиска с различной эффективностью.

Последовательный поиск элемента среди элементов множества подразумевает исследование элементов множестваA в том порядке, в каком они встречаются. Эта стратегия поиска является наиболее очевидной и самой простой.

Поиск начинается с первого элемента и продолжается до тех пор, пока не будет найден нужный элемент. После этого алгоритм останавливается.

Очевидно, что наихудшая оценка сложности алгоритма линейно зависит от мощности множества A (). Оценимсреднюю сложность последовательного поиска.

Для нахождения элемента требуетсяi сравнений. Для вычисления среднего времени поиска необходимо знать информацию о частоте обращений к каждому элементу множества. Предположим, что в некотором вычислительном эксперименте к каждому элементу обращаются с одинаковой частотой (частота обращений распределена равномерно). Тогда средняя сложность алгоритма для n независимых испытаний (n процедур поиска), будет равна , асредняя сложность алгоритма , т.е линейна.

Рассмотрим распределение частот обращения к элементам в общем случае (например, в некоторой поисковой системе). Пусть - обозначает приведенную частоту обращения к элементу(для заданного цикла испытаний). Если для каждого элемента известно количество поисков (, тогда.

В этом случае средняя сложность можно оценить по формуле . Средняя сложность алгоритма поиска в общем случае зависит от распределения частот. Дж. Зипф заметил, чтоk-е наиболее употребительное в тексте на естественном языке слово встречается с частотой приблизительно обратно пропорционально k, т.е . Нормирующая константа выбирается из условия

Пусть элементы множества упорядочены согласно указанным частотам, т.е . Тогдаи среднее время успешного поиска составит. Что существенно эффективнее, чем при неотсортированном размещении данных.

Последний пример показывает, что даже простой последовательный поиск при удачном выборе структуры данных (отсортированный массив) может существенно повысить эффективность алгоритма поиска. На рисунке 19 приведены зависимости оценок сложностей алгоритмов. На практике это общепринятая стратегия время от времени переупорядочивать данные.

Рис. 19

Логарифмический поиск

Логарифмический поиск (бинарный, метод деления пополам) данных применим к сортированному множеству элементов размещение которого может быть реализовано на смежной памяти.

Идея метода заключается в том, что для большей эффективности поиска элемента (например, необходимо построить алгоритм так, чтобы путь к нужному элементу был как можно короче.

Последнее можно реализовать, если поиск начинать с середины множества, т.е. с элемента . Если, но нужный элемент находится справа от, иначе наоборот. Поделив пополам правое или левое подмножество мы еще раз уменьшим пространство поиска в двое. Данную процедуру можно продолжать до тех пор, пака не найдем нужный элемент.

Естественной геометрической интерпретацией бинарного поиска является двоичное дерево сравнений.

Определение 3.2. Двоичное дерево называется деревом сравнений, если для любой его вершины выполняется условие:

{вершины левого поддерева}<вершина корня<{вершины правого поддерева}.

На рисунке 20 показан пример двоичного дерева сравнений для сортированного множества A={3, 5, 7, 9, 12, 19, 27, 44}

Средняя сложность бинарного поиска среди элементов сравнима с высотой двоичного дерева, которую можно оценить величиной. Значит сложность логарифмического поиска можно оценить величиной.