Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Задача поиска. Алгоритмы линейного поиска.
Общая постановка. В заданной совокупности элементов требуется найти элемент, обладающий заданным набором свойств. Важнейший частный случай. Задан массив x, нужно определить имеет ли в нем элемент, совпадающий с заданным числом a. Если такой элемент обнаружен, то в качестве дополнительной информации следует получить номер совпадающего с заданным элемента массива a) Классический алгоритм Предлагается очевидный подход к решению задачи: последовательное сравнение каждого очередного элемента массива с заданным. Такой способ называется линейным поиском. б) Быстрый алгоритм Идея быстрого алгоритма состоит в том, что выражения flag и x[i]=a эквивалентны. Следовательно, в условии в заголовке цикла вместо not flag можно использовать x[i]<>a, и отказаться от использования индикатора flag. в) Алгоритм с барьером Следующее улучшение состоит в упрощении условия в заголовке цикла. Целевым является условие x[i]<>a, которое убрать или упростить невозможно. Следовательно, можно рассматривать только условие i<=N, обеспечивающие прекращение просмотра после исчерпания всех элементов цикла. Идея состоит в выставлении в конце массива «барьера». Для этого в массив добавляется N+1 элемент, значение которого приравнивается к искомому. В алгоритмах линейного поиска максимальное количество операций, которое приходится проделать для определения результата поиска пропорционально N.
Бинарный поиск. Если данные упорядочены, то поиск можно сделать значительно более эффективным. Если x[i]<=x[i+1], i=1,2,…,N-1, то массив называется упорядоченным (отсортированным) по возрастанию. Искомый элемент сравнивается со средним элементом массива. Если они совпадают, то задача уже решена. Так как массив упорядочен, то при не совпадении элементов, в дальнейшем поиске можно не рассматривать одну из половин массива. А именно, если средний элемент массива больше искомого, то все элементы, расположенные правее его, также будут больше искомого и дальнейший поиск следует осуществлять в левой половине массива. В противном случае, если средний элемент массива меньше искомого, то все элементы, расположенные левее, будут также меньше его и дальнейший поиск следует выполнять в правой половине массива. Итак, во время поиска приходится повторять следующие действия: 1) выбирать средний элемент массива; 2) сравнивать его с искомым; 3) при необходимости уменьшать рассматриваемую часть массива в два раза выбором его правой или левой половины. Так как начальный и конечный элементы рассматриваемой части массива при отбрасывании одной из половин массива будут изменяться, то для записи алгоритма следует использовать переменные, имеющие смысл номеров начального (левого) L и конечного (правого) R элементов массива. Поскольку в начале рассматривается весь массив, то L=1, а R=N. Номер среднего элемента M можно найти стандартным способом: M=(R+L) div 2. Оценим максимальное количество операций, которые потребуется выполнить для решения задачи поиска в алгоритме бинарного поиска. На первом шаге количество K рассматриваемых элементов массива равно N После первого шага количество K рассматриваемых элементов массива уменьшается в два раза K=N/2. После второго шага - в четыре раза Вообще, после шага с номером m: В худшем случае процесс поиска закончится после того, как останется один элемент: . Отсюда: Оценка количества операций, которые должны быть выполнены для получения результата, характеризует сложность алгоритма. Сложность алгоритма линейного поиска пропорциональна N, а сложность алгоритма бинарного поиска пропорциональна
|
Последнее изменение этой страницы: 2019-04-19; Просмотров: 208; Нарушение авторского права страницы