Алгоритмы поиска и их программа

I ГЛАВА ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1. 
   АЛГОРИТМЫ ПОИСКА
   

Алгоритм поиска-это поисковая проблема, которую решает любой алгоритм, то есть для получения данных, хранящихся в некотором контенте данных или вычисляемых в поле поиска проблемной области или дискретные или непрерывные значения. Конкретные применения поисковых алгоритмов включают: Элемент произвольной информации (или структуры) отличается от другого одним признаком. Этот символ называется ключом. Ключ может быть неповторяющимся, то есть именно этот ключ применяется к одному существующему элементу в структуре. Такой ключ называется первичным. Повторяемый ключ для определенной группы элементов называется вторичным ключом, по этому ключу также можно организовать поиск. Ключи элементов данных могут быть собраны в отдельном месте (в другой таблице) или храниться сами в каком-то поле в отдельной записи. Такой выделенный или хранящийся в отдельном файле называется внешним ключом. Если ключ находится в записи, то он называется внутренним ключом.
Поиск по заданному аргументу называется алгоритмом, определяемым заданным ключом аргумента. Результат работы алгоритма поиска может располагаться в этой информации, а может и не присутствовать в таблице. Состояние недоступности информации может произойти в двух действиях:
1. При определении отсутствия заданного значения;
2. При подстановке заданного значения в таблицу.
Например, пусть нам дан K в качестве ключа элемента списка. Каждый ключ K(I) содержит r(I)-информацию. Аргумент поиска - Key. Ему соответствует реквизит записи. В зависимости от структуры данных в таблице различают несколько форм поиска.
Есть два разных подхода к решению этой проблемы: последовательный поиск и
индексированный серийный поиск. Рассмотрим эти алгоритмы поиска. Алгоритмы поиска можно классифицировать в зависимости от поисковой системы. Линейный поиск алгоритмы проверяют каждую запись на предмет линейной связи с целевым ключом. Двоичный или полуинтервальный поиск, нацельтесь несколько раз на центр структуры поиска и разделите поле поиска пополам. Алгоритмы сравнительного поиска улучшают линейный поиск за счет последовательного удаления записей на основе сравнения ключей до тех пор, пока не будет найдена целевая запись, и могут применяться к структурам данных в указанном порядке. Алгоритмы числового поиска работают на основе свойств чисел в структурах данных, которые используют числовые ключи. Наконец, хеширование-это хеш-функция, основанная на сопоставлении ключей непосредственно для записей. Поиск за пределами линейного поиска требует, чтобы данные были в некотором порядке.
Алгоритмы часто оцениваются по их вычислительная сложность или максимальное теоретическое время выполнения. Двоичные функции поиска имеют максимальную сложность, например о(log N), или логарифмическое время. Это означает, что максимальное количество операций, необходимых для поиска цели поиска, является логарифмической функцией размера поля поиска.

2.