Читать курсовая по Отсутствует: "Создание программы при помощи языка программирования С" Страница 2

(Назад) (Cкачать работу)

1.

Постановка задачи Одной из важнейших операций в обработке данных является поиск. Поиск - получение конкретного фрагмента или фрагментов информации из больших объемов ранее сохраненных данных.

Существует не так много различных методов поиска в массивах данных (списках). Рассмотрим и сравним возможности основных методов:

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

. Бинарный поиск.

. Интерполяционный поиск.

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

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

Средняя сложность t поиска элементов в списке a[0],a[1],a[2]…a[n], при условии, что частота обращения к каждому элементу списка распределена равномерно, будет:

где: - количество элементов в массиве;

t - средняя сложность поиска (время поиска).

Линейный поиск прост в реализации и применим, если список содержит мало элементов.

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

Для больших и сортированных массивов данных необходимо применять более эффективные методы поиска, чем последовательный поиск.

1.1 Бинарный поиск Бинарный поиск - алгоритм поиска элемента в отсортированном массиве, использующий дробление массива на половины.

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

Средняя сложность t поиска элементов в списке a[0],a[1],a[2]…a[n], при условии, что частота обращения к каждому элементу списка распределена равномерно, будет:

где: - количество элементов в массиве;- средняя сложность поиска (время поиска).

Так, если список содержит 1024 элемента, то количество операций, необходимых для нахождения ключа будет равно:

Используя последовательный поиск, в среднем пришлось бы затратить 512 операций. Что значительно превышает значение, полученное при использовании бинарного поиска.

Недостаток бинарного поиска является в хранении списка в обязательно отсортированном виде, что усложняет задачу добавление и исключения элементов из списка.

1.3 Интерполяционный поискАлгоритм интерполяционного поиска производит предсказание местонахождения элемента. Поиск происходит подобно бинарному поиску, но вместо деления области поиска на две части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Если мы знаем, что K находится между Kl и Ku, следующую проверку мы будем делать примерно на расстоянии от l (в предположении, что ключи представляют собой числовые значения, близкие к арифметической прогрессии), где:

K - ключ поиска;

l - индекс левой границы массива (отрезка массива);

u - индекс правой границы массива (отрезка массива);

Kl - значение элемента массива на позиции l;

Ku - значение элемента массива на позиции u.

Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный поиск. В то время как один шаг бинарного поиска

Похожие работы