Анализ алгоритмов быстрого поиска в словаре

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
Учреждение образования «Гродненский государственный
университет имени Янки Купалы»

Факультет математики и информатики

Кафедра системного программирования и компьютерной безопасности


АНАЛИЗ АЛГОРИТМОВ БЫСТРОГО ПОИСКА В СЛОВАРЕ
Иванюкович Дарьи Петровны
студентки 3 курса 6 группы

Руководитель

Сюрин В.Н.
Гродно 2013
СОДЕРЖАНИЕ
Введение ………………………………………………………………………..3
Часть 1. Теоретические сведения об алгоритмах…………………………….5
1.1. Метод грубой силы……………………………………………………5
1.2. Алгоритм Рабина……………………………………………………...6
1.3. Алгоритм Кнута - Морриса – Пратта………………………………..7
1.4. Бинарный поиск……………………………………………………….7
1.5. Интерполяционный поиск……………………………………………9
1.6. 2-3 деревья……………………………………………………………10
1.7. Алгоритм Хорспула………………………………………………….11
1.8. В-деревья……………………………………………………………..13
Часть 2. Экспериментальный анализ алгоритмов…………………………..14
2.1. Суть эксперимента……………………………………………………14
2.2. Результаты и анализ эксперимента…………………….…………..…15
Заключение…………………………………………………………………….17
Список использованной литературы………………………………….……..19
Введение
Задача поиска связана с нахождением заданного значения, называемого ключом поиска (search key), среди заданного множества (или мультимножества). Существует огромное количество алгоритмов поиска, так что есть из чего выбирать. Их сложность варьируется от самых простых алгоритмов поиска методом последовательного сравнения, до чрезвычайно эффективных, но ограниченных алгоритмов бинарного поиска, а также алгоритмов, основанных на представлении базового множества в иной, более подходящей для выполнения поиска форме. Последние из упомянутых здесь алгоритмов имеют особое практическое значение, поскольку применяются в реально действующих приложениях, выполняющих выборку и хранение массивов информации в огромных базах данных. Для решения задачи поиска также не существует единого алгоритма, который бы наилучшим образом подходил для всех случаев. Некоторые из алгоритмов выполняются быстрее остальных, но для их работы требуется дополнительная оперативная память. Другие выполняются очень быстро, но их можно применять только для предварительно отсортированных массивов, и т.п. В отличие от алгоритмов сортировки в алгоритмах поиска нет проблемы устойчивости, но при их использовании могут возникать другие сложности. В частности, в тех приложениях, где обрабатываемые данные могут часто изменяться, причем количество изменений сравнимо с количеством операций поиска, поиск следует рассматривать в неразрывной связи с двумя другими операциями — добавления элемента в набор данных и удаления из него. В подобных ситуациях необходимо видоизменить структуры данных и алгоритмы так, чтобы достигалось равновесие между требованиями, выдвигаемыми к каждой операции. Кроме того, организация очень больших наборов данных с целью выполнения в них эффективного поиска (а также добавления и удаления элементов) представляет собой чрезвычайно сложную задачу, решение которой особенно важно с точки зрения практического применения.