Лабораторная работа 8.
Тема: Алгоритмы поиска и выборки.
Задания:
1. Написать программу реализующую алгоритм последовательного поиск целевого значения из выборки N чисел (использовать любой язык программирования).
2. Написать программу реализующую алгоритм двоичного поиска целевого значения из выборки N чисел (использовать любой язык программирования).
3. Провести анализ наихудшего и среднего случаев.
4. Оформить отчет в MSWord и показать работающую программу преподавателю.
Теоретический минимум.
Алгоритмы поиска и выборки
Поиск необходимой информации в списке — одна из фундаментальныхзадач теоретического программирования. При обсуждении алгоритмов поиска мы предполагаем, что информация содержится в записях, составляющих некоторый список, который представляет собой массив данных в программе. Записи, или элементы списка, идут в массиве последовательно и между ними нет промежутков. Номера записей в списке идут от 1 доN— полного числа записей. В принципе записи могут быть составлены из полей, однако нас будут интересовать значения лишь одного из этих полей, называемого ключом. Списки могут быть не отсортированными или отсортированными по значению ключевого поля. В не отсортированном списке порядок записей случаен, а в отсортированном они идут в порядке возрастания ключа.
Поиск нужной записи в не отсортированном списке сводится к просмотру всего списка до того, как запись будет найдена. Это простейший из алгоритмов поиска. Мы увидим, что этот алгоритм не очень эффективен, однако он работает на произвольном списке.
В отсортированном списке возможен также двоичный поиск. Двоичный поиск использует преимущества, предоставляемые имеющимся упорядочиванием, для того, чтобы отбрасывать за одно сравнение больше одного элемента. В результате поиск становится более эффективным.
С поиском конкретного значения связана задача выборки, в которой требуется найти элемент, удовлетворяющий некоторым условиям. Скажем, нам может понадобиться пятый по величине элемент, седьмой с конца или элемент со средним значением. Мы обсудим два подхода к этой задаче.
1. Последовательный поиск
В алгоритмах поиска нас интересует процесс просмотра списка в поисках некоторого конкретного элемента, называемого целевым. При последовательном поиске мы всегда будем предполагать, хотя в этом и нет особой необходимости, что список не отсортирован, поскольку некоторые алгоритмы на отсортированных списках показывают лучшую производительность. Обычно поиск производится не просто для проверки того, что нужный элемент в списке имеется, но и для того, чтобы получить данные, относящиеся к этому значению ключа. Например, ключевое значение может быть номером сотрудника или порядковым номером, или любым другим уникальным идентификатором. После того, как нужный ключ найден, программа может, скажем, частично изменить связанные с ним данные или просто вывести всю запись. Во всяком случае, перед алгоритмом поиска стоит важная задача определения местонахождения ключа. Поэтому алгоритмы поиска возвращают индекс записи, содержащей нужный ключ. Если ключевое значение не найдено, то алгоритм поиска обычно возвращает значение индекса, превышающее верхнюю границу массива. Для наших целей мы будем предполагать, что элементы списка имеют номера от 1 доN.Это позволит нам возвращать 0 в случае, если целевой элемент отсутствует в списке. Для простоты мы предполагаем, что ключевые значения не повторяются.
Алгоритм последовательного поиска последовательно просматривает по одному элементу списка, начиная с первого, до тех пор, пока не найдет целевой элемент. Очевидно, что чем дальше в списке находится конкретное значение ключа, тем больше времени уйдет на его поиск. Это следует помнить при анализе алгоритма последовательного поиска.
Вот как выглядит полный алгоритм последовательного поиска.
SequentialSearch(list.target,N)listсписок для просмотра
targetцелевое значениеNчисло элементов в списке
for i=l to N do
if (target=list[i])
return i
end if
end for
return 0
Анализ наихудшего случая
У алгоритма последовательного поиска два наихудших случая. В первом случае целевой элемент стоит в списке последним. Во втором его вовсе нет в списке. Посмотрим, сколько сравнений выполняется в каждом из этих случаев. Мы предположили, что все ключевые значения в списке уникальны, и поэтому если совпадение произошло в последней записи, то все предшествующие сравнения были неудачными. Однако алгоритм проделывает все эти сравнения пока не дойдет до последнего элемента. В результате будет проделаноNсравнений, гдеN— число элементов в списке.
Чтобы проверить, что целевое значение в списке отсутствует, его придется сравнить со всеми элементами списка. Если мы пропустим какой-то элемент, то не сможем выяснить, отсутствует ли целевое значение в списке вообще или оно содержится в каком-то из пропущенных элементов. Это означает, что для выяснения того, что ни один из элементов не является целевым, нам потребуетсяNсравнений.
Так чтоNсравнений необходимо как для того, чтобы найти значение, содержащееся в последнем элементе списка, так и для того, чтобы выяснить, что целевого значения в списке нет. Ясно, чтоNдает верхнюю границу сложности любого алгоритма поиска, поскольку, если сравнений большеN,то это означает, что сравнение с каким-то элементом выполнялось по крайней мере дважды, а значит была проделана лишняя работа, и алгоритм можно улучшить.
Между понятиями верхней границы сложности и сложности в наихудшем случае есть разница. Верхняя граница присуща самой задаче, а понятие наихудшего случая относится к решающему ее конкретному алгоритму.
Анализ среднего случая
Для алгоритмов поиска возможны два средних случая. В первом предполагается, что поиск всегда завершается успешно, во втором — что иногда целевое значение в списке отсутствует.
Если целевое значение содержится в списке, то оно может занимать одно изNвозможных положений: оно может быть первым, вторым, третьим, четвертым и так далее. Мы будем предполагать все эти положения равновероятными, т.е. вероятность встретить каждое из них равна 1/N.
Прежде, чем читать дальше, ответьте на следующие вопросы.
• • Сколько сравнений требуется, если искомый элемент стоит в списке первым?
• • А если вторым?
• • А если третьим?
• • А если последним изNэлементов?
Если Вы внимательно посмотрели на алгоритм, то Вам несложно определить, что ответы будут выглядеть 1, 2, 3 иNсоответственно. Это означает, что для каждого изNслучаев число сравнений совпадает с номером искомого элемента. В результате для сложности в среднем случае мы получаем равенство
Если мы допускаем, что целевого значения может не оказаться в списке, то количество возможностей возрастает доN+ 1.
Как мы уже видели, при отсутствии элемента в списке его поиск требуетNсравнений. Если предположить, что всеN+ 1возможностей равновероятны, то получится следующая выкладка:
(КогдаNстановится очень большим, значение1/(N+1) оказывается близким к 0.)
Видно, что допущение о возможности отсутствия элемента в списке увеличивает сложность среднего случая лишь на 1/2. Ясно, что по сравнению с длиной списка, которая может быть очень велика, эта величина пренебрежимо мала.
2. Двоичный поиск
При сравнении целевого значения со средним элементом отсортированного списка возможен один из трех результатов: значения равны, целевое значение меньше элемента списка, либо целевое значение больше элемента списка. В первом, и наилучшем, случае поиск завершен. В остальных двух случаях мы можем отбросить половину списка.
Когда целевое значение меньше среднего элемента, мы знаем, что если оно имеется в списке, то находится перед этим средним элементом. Когда же оно больше среднего элемента, мы знаем, что если оно имеется в списке, то находится после этого среднего элемента. Этого достаточно, чтобы мы могли одним сравнением отбросить половину списка. При повторении этой процедуры мы сможем отбросить половину оставшейся части списка. В результате мы приходим к следующему алгоритму
BinarySearch(list.target,N) listсписок для просмотра targetцелевое значение Nчисло элементов в списке
start=l
end=N
while start<=end do
middle=(start+end)/2
select(Compare(list[middle].target)) from
case -1: start=middle+l
case 0: return middle
case 1: end=middle-l
end select
end while
return 0
В этом алгоритме переменной start присваивается значение, на 1 большее, чем значение переменнойmiddle, если целевое значение превышает значение найденного среднего элемента. Если целевое значение меньше значения найденного среднего элемента, то переменнойendприсваивается значение, на 1 меньше, чем значение переменнойmiddle. Сдвиг на 1 объясняется тем, что в результате сравнения мы знаем, что среднее значение не является искомым, и поэтому его можно исключить из рассмотрения.
Всегда ли цикл останавливается? Если целое значение найдено, то ответ, разумеется, утвердительный, поскольку выполняется оператор return. Если нужное значение не найдено, то на каждой итерации цикла либо возрастает значение переменнойstart, либо уменьшается значение переменойend. Это означает, что их значения постепенно сближаются. В какой-то момент эти два значения становятся равными, и цикл выполняется еще один раз при соблюдении равенстваstart=end=middle. После этого прохода (если элемент с этим индексом не является искомым) либо переменнаяstartокажется на 1 больше, чемendиmiddle, либо наоборот, переменнаяendокажется на 1 меньше, чемstartиmiddle. В обоих случаях условие циклаwhileложным, и цикл больше выполнятся не будет. Поэтому выполнение цикла завершается всегда.
Возвращает ли этот алгоритм правильный результат? Если целевое значение найдено, то ответ безусловно утвердительный, поскольку выполнен оператор return. Если же средний элемент оставшейся части списка не подходит, то на каждом подходе цикла происходит исключение половины оставшихся элементов, поскольку все они либо чересчур велики, чересчур малы. Ранее мы говорили, что в результате мы придем к единственному элементу, который следует проверить. Если это нужный нам ключ то будет возвращено значение переменнойmiddle. Если же значение ключа отлично от искомого, то значение переменнойstartпревысит значениеendили наоборот, значение переменнойendстанет меньше значенияstart. Если бы целевое значение содержалось в списке, то оно было бы меньше или больше значения элементаmiddle. Однако значения переменныхstartиendпоказывают, что предыдущие сравнения исключили все остальные возможности, и поэтому целевое значение отсутствует в списке. Значит цикл завершит работу, а возращенное значение будет равно нулю, что указывает на неудачу поиска. Таким образом, алгоритм возвращает верный ответ.
Поскольку алгоритм всякий раз делит список пополам, мы будем предполагать при анализе, что N=2k-1 для некоторого k. Если это так, то сколько элементов останется при втором проходе? А третьем? Вообще говоря, ясно, что если на некотором подходе цикл имеет дело со списком из 2j-1 элементов, то в первой половине списка 2j-1-1 элементов, один элемент в середине, и 2j-1-1 элементов во второй половине списка. Поэтому к следующему проходу остаётся 2j-1-1 элемент (при
). Это предложение позволяет упростить последующий анализ, но необходимости в нем нет.
Анализ наихудшего случая.
В предыдущем абзаце мы показали, что степень двойки в длине оставшейся части списка при всяком проходе цикла уменьшится на 1, а также, что последняя итерация цикла производится, кода размер оставшейся части становится равным 1, а это происходит при j=1 (так как 21-1=1). Это означает, что при N=2k-1 число проходов не превышает k. Решая последние уравнение относительно k, мы заключаем, что в наихудшем случае число проходов равно k=log2(N+1).
В анализе может помочь и дерево для процесса поиска. В узлах дерева решение стоят элементы, которые проверяются на соответствующем проходе. Элементы, проверка которых будет осуществляться в том случае, если целевое значение меньше текущего элемента, а сравниваемые в случае, если целевое значение больше текущего – в правом поддереве. Дерево решение для списка из 7 элементов изображено на рисунке1. В общем случае дерево относительно сбалансировано, поскольку мы всегда выбираем середину различных частей списка. Поэтому для подсчета числа сравнений мы можем воспользоваться формулами для бинарных деревьев.
 |
Поскольку мы предполагаем, что N=2k-1, соответствующие дерево решение будет всегда полным. В нем будет k уровней, где k=log2(N+1). Мы делаем по одному сравнению на каждом уровне, поэтому полное число сравнений не превосходит log2(N+1).
Рис. 1. Дерево решений для поиска в списке из семи элементов
Анализ среднего случая(изучить самостоятельно)
2.3.Выборка
Иногда нам нужен элемент из списка, обладающий некоторыми специальными свойствами, а не имеющий некоторое конкретное значение. Другими словами, вместо записи с некоторым конкретным значением поля нас интересует, скажем, запись с наибольшим, наименьшим или средним значением этого поля. В более общем случае нас может интересовать запись сК-ыыпо величине значением поля.
Один из способов найти такую запись состоит в том, чтобы отсортировать список в порядке убывания; тогда запись сК-ышпо величине значением окажется наК-оыместе. На это уйдет гораздо больше сил, чем необходимо: значения, меньшие искомого, нас, на самом деле, не интересуют. Может пригодиться следующий подход: мы находим наибольшее значение в списке и помещаем его в конец списка. Затем мы можем найти наибольшее значение в оставшейся части списка, исключая уже найденное. В результате мы получаем второе по величине значение списка, которое можно поместить на второе с конца место в списке. Повторив эту процедуруКраз, мы найдемК-оепо величине значение. В результате мы приходим к алгоритму
FindKthLargest(list,K,N)
listсписок для просмотра
Nчисло элементов в списке
Кпорядковый номер по величине требуемого элемента
for i=l to К do
largest=list[1]
largestLocation=1
for j=2 to N-(i-l) do
if list [j]>largest then
largest=list[j]largestLocation=jend if
end for
Swap(list[N-(i-l)],list[largestLocation])
end for
return largest
Какова сложность этого алгоритма? На каждом проходе мы присваиваем переменной largest значение первого элемента списка, а затем сравниваем эту переменную со всеми остальными элементами. При первом проходе мы делаемN— 1сравнение, на втором — на одно сравнение меньше. НаК-омпроходе мы делаемN— Ксравнений. Поэтому для поискаК-огопо величине элемента нам потребуется
сравнений, что по порядку величины равноO(KN).Следует заметить также, что еслиКбольше, чемN/2,то поиск лучше начинать с конца списка. Для значенийКблизких к 1 или кNэтот алгоритм довольно эффективен, однако для поиска значений из середины списка есть и более эффективные алгоритмы.
Поскольку нам нужно лишьК-оепо величине значение, точное местоположение большихК—\элементов нас на самом деле не интересует, нам достаточно знать, что они больше искомого. Для всякого элемента из списка весь список распадается на две части: элементы, большие взятого, и меньшие элементы. Если переупорядочить элементы в списке так, чтобы все большие шли за выбранным, а все меньшие — перед ним, и при этом выбранный элемент окажется наР-омместе, то мы будем знать, что он Р-ый по величине. Такое переупорядочивание потребует сравнения выбранного элемента со всеми остальными, т.е.N— 1 сравнений. Если нам повезло иР = К,то работа закончена. ЕслиК < Р,то нам нужно некоторое большее значение, и проделанную процедуру можно повторить со второй частью списка. ЕслиК>Р,то нам нужно меньшее значение, и мы можем воспользоваться первой частью списка; при этом, однако,Кследует уменьшить на число откинутых во второй части элементов. В результате мы приходим к следующему рекурсивному алгоритму.
KthLargestRecursive(list.start,end,К)
listсписок для просмотра
startиндекс первого рассматриваемого элемента
endиндекс последнего рассматриваемого элемента
Кпорядковый номер по величине требуемого элемента
if start< end then
Partitiondist, start,end.middle) if middle=K then
return list[middle] else
if K<middle then
return KthLargestRecursive(list,middle+1,end,K) else
return KthLargestRecursive(list,start,middle-l,K-middle)
end if
end if
endif
Если предположить, что в среднем при разбиении список будет де литься на две более или менее равные половины, то число сравнений будет приблизительно равно
N + N/2 + N/4 + N/8+…+1 , т.е. 2N.Поэтому сложность алгоритма линейна и не зависит отК.
Литература:
1. Дж. Макконелл Анализ алгоритмов. Вводный курс
2. Д.Э. Кнут Искусство программирования. Том 3.
superbotanik.net
Реферат на тему:
|
Поиск A* (произносится «А звезда» или «А стар», от англ. A star) — в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).
Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).
Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками.
Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Это по сути было расширение алгоритма Эдсгера Дейкстры, созданного в 1959 году. Он достигал более высокой производительности (по времени) с помощью эвристики. В их работе он упоминается как «алгоритм A». Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.
Обобщением для него является двунаправленный эвристический алгоритм поиска.
В 1964 году Нильс Нильсон изобрел эвристический подход к увеличению скорости алгоритма Дейкстры. Этот алгоритм был назван А1. В 1967 году Бертрам Рафаэль сделал значительные улучшения по этому алгоритму, но ему не удалось достичь оптимальности. Он назвал этот алгоритм A2. Тогда в 1968 году Петр Э. Харт представил аргументы, которые доказывали, что A2 был оптимальным при использовании последовательной эвристики лишь с незначительными изменениями. В его доказательство алгоритма также включен раздел, который показывал, что новый алгоритм A2 был возможно лучшим алгоритмом, учитывая условия. Таким образом, он обозначил новый алгоритм в синтаксисе звездочкой, он начинается на А и включал в себя все возможные номера версий.
Пустые кружки в узлах принадлежат открытому списку, красные/зеленые относятся к закрытому списку.
A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного алгоритма (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) — это стоимость пути от начальной вершины, а не от предыдущей, как в жадном алгоритме). В начале работы просматриваются узлы, смежные с начальной; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью.
Чем меньше эвристика h(x), тем больше приоритет (поэтому для реализации очереди можно использовать сортирующие деревья).
function A*(start,goal) % множество уже пройденных вершин var closed := the empty set % множество частных решений var q := make_queue(path(start)) while q is not empty var p := remove_first(q) var x := the last node of p if x in closed continue if x = goal return p add x to closed % добавляем смежные вершины foreach y in successors(x) enqueue(q, p, y) return failureМножество уже пройденных вершин можно опустить (при этом алгоритм превратится в поиск по дереву решений), если известно, что решение существует, либо если структура successors умеет отсекать циклы.
Примером алгоритма A* в действии, где узлы – это города, связанные с дорогами и Н (х) является самым коротким расстоянием до целевой точки:
Ключ: зеленый - начало, синий - цель, оранжевый - посещенные узлы.
Примечание: Этот пример использует запятую как десятичный разделитель.
Как и алгоритм поиска в ширину, A* является полным в том смысле, что он всегда находит решение, если таковое существует.
Если эвристическая функция h допустима, то есть никогда не переоценивает действительную минимальную стоимость достижения цели, то A* сам является допустимым (или оптимальным), также при условии, что мы не отсекаем пройденные вершины. Если же мы это делаем, то для оптимальности алгоритма требуется, чтобы h(x) была ещё и монотонной, или преемственной эвристикой. Свойство монотонности означает, что если существуют пути A—B—C и A—C (не обязательно через B), то оценка стоимости пути от A до C должна быть меньше либо равна сумме оценок путей A—B и B—C. (Монотонность также известна как неравенство треугольника: одна сторона треугольника не может быть длиннее, чем сумма двух других сторон.) Математически, для всех путей x, y (где y — потомок x) выполняется:
A* также оптимально эффективен для заданной эвристики h. Это значит, что любой другой алгоритм исследует не меньше узлов, чем A* (за исключением случаев, когда существует несколько частных решений с одинаковой эвристикой, точно соответствующей стоимости оптимального пути).
В то время как A* оптимален для «случайно» заданных графов, нет гарантии, что он сделает свою работу лучше, чем более простые, но и более информированные относительно проблемной области алгоритмы. Например, в неком лабиринте может потребоваться сначала идти по направлению от выхода, и только потом повернуть назад. В этом случае обследование вначале тех вершин, которые расположены ближе к выходу (по прямой дистанции), будет потерей времени.
В общем говоря, поиск в глубину и поиск в ширину являются двумя частными случаями алгоритма A*. Для поиска в глубину возьмём глобальную переменную-счётчик С, инициализировав её неким большим значением. Всякий раз при раскрытии вершины будем присваивать значение счётчика смежным вершинам, уменьшая его на единицу после каждого присваивания. Таким образом, чем раньше будет открыта вершина, тем большее значение h(x) она получит, а значит, будет просмотрена в последнюю очередь. Если положить h(x) = 0 для всех вершин, то мы получим ещё один специальный случай — алгоритм Дейкстры.
Существует несколько особенностей реализации и приёмов, которые могут значительно повлиять на эффективность алгоритма. Первое, на что не мешает обратить внимание — это то, как очередь с приоритетом обрабатывает связи между вершинами. Если вершины добавляются в неё так, что очередь работает по принципу LIFO, то в случае вершин с одинаковой оценкой A* «пойдёт» в глубину. Если же при добавлении вершин реализуется принцип FIFO, то для вершин с одинаковой оценкой алгоритм, напротив, будет реализовывать поиск в ширину. В некоторых случаях это обстоятельство может оказывать существенное значение на производительность.
В случае, если по окончании работы от алгоритма требуется маршрут, вместе с каждой вершиной обычно хранят ссылку на родительский узел. Эти ссылки позволяют реконструировать оптимальный маршрут. Если так, тогда важно, чтобы одна и та же вершина не встречалась в очереди дважды (имея при этом свой маршрут и свою оценку стоимости). Обычно для решения этой проблемы при добавлении вершины проверяют, нет ли записи о ней в очереди. Если она есть, то запись обновляют так, чтобы она соответствовала минимальной стоимости из двух. Для поиска вершины в сортирующем дереве многие стандартные алгоритмы требуют времени O(n). Если усовершенствовать дерево с помощью хеш-таблицы, то можно уменьшить это время.
Алгоритм A* и допустим, и обходит при этом минимальное количество вершин, благодаря тому, что он работает с «оптимистичной» оценкой пути через вершину. Оптимистичной в том смысле, что, если он пойдёт через эту вершину, у алгоритма «есть шанс», что реальная стоимость результата будет равна этой оценке, но никак не меньше. Но, поскольку A* является информированным алгоритмом, такое равенство может быть вполне возможным.
Когда A* завершает поиск, он, согласно определению, нашёл путь, истинная стоимость которого меньше, чем оценка стоимости любого пути через любой открытый узел. Но поскольку эти оценки являются оптимистичными, соответствующие узлы можно без сомнений отбросить. Иначе говоря, A* никогда не упустит возможности минимизировать длину пути, и потому является допустимым.
Предположим теперь, что некий алгоритм B вернул в качестве результата путь, длина которого больше оценки стоимости пути через некоторую вершину. На основании эвристической информации, для алгоритма B нельзя исключить возможность, что этот путь имел и меньшую реальную длину, чем результат. Соответственно, пока алгоритм B просмотрел меньше вершин, чем A*, он не будет допустимым. Итак, A* проходит наименьшее количество вершин графа среди допустимых алгоритмов, использующих такую же точную (или менее точную) эвристику.
Временна́я сложность алгоритма A* зависит от эвристики. В худшем случае, число вершин, исследуемых алгоритмом, растёт экспоненциально по сравнению с длиной оптимального пути, но сложность становится полиномиальной, когда эвристика удовлетворяет следующему условию:
где h* — оптимальная эвристика, то есть точная оценка расстояния из вершины x к цели. Другими словами, ошибка h(x) не должна расти быстрее, чем логарифм от оптимальной эвристики.
Но ещё бо́льшую проблему, чем временна́я сложность, представляют собой потребляемые алгоритмом ресурсы памяти. В худшем случае ему приходится помнить экспоненциальное количество узлов. Для борьбы с этим было предложено несколько вариаций алгоритма, таких как алгоритм A* с итеративным углублением (iterative deeping A*, IDA*), A* с ограничением памяти (memory-bounded A*, MA*), упрощённый MA* (simplified MA*, SMA*) и рекурсивный поиск по первому наилучшему совпадению (recursive best-first search, RBFS).
Классическим примером служит игра Lines (Color Lines, в народе Шарики), изобретённая Олегом Дёминым, Геннадием Денисовым и Игорем Ивкиным и разработанная российской компанией Gamos в 1992 году.
В данной игре на экране показано квадратное поле 9×9 клеток, в случайные клетки на котором программа выставляет три шарика разных цветов. Всего 7 возможных цветов. За один ход игрок может передвинуть один шарик, выделив его и указав его новое местоположение. Для совершения хода необходимо, чтобы между начальной и конечной клетками существовал путь из свободных клеток. Цель игры состоит в удалении максимального количества шариков, которые исчезают при выстраивании шариков одного цвета по пять и более в ряд (по горизонтали, вертикали или диагонали). При исчезновении ряда шариков новые три шарика не выставляются. В остальных случая каждый ход выставляются новые три шарика. Игрок может видеть заранее три шарика, которые появятся в следующем ходу.
wreferat.baza-referat.ru
Главная » Рефераты » Текст работы «Алгоритмы поиска подстроки в строке - Программирование, компьютеры и кибернетика»
3
- В в е д е н и е -Цель курсовой работы: Изучить и проанализировать алгоритмы поиска подстроки в строке, и рассмотреть ряд практических задач на данную тематику. Задачи курсовой работы: изучить задачи связанные с проблемой поиска подстроки в строке, дать основные определения; рассмотреть применение различных алгоритмов поиска подстроки в строке на практике; написать программный код, реализующий один из алгоритмов поиска подстроки в строке. Тема моей курсовой работы является актуальной и на сегодняшний день, те, кому приходиться часто работать с текстовыми редакторами, знают цену функции нахождения нужных слов в тексте, существенно облегчающей редактирование документов и поиск нужной информации. Действительно, современные программы обработки текста приучили нас к такой удобной возможности, как поиск и замена фрагментов, и если разрабатывать подобную программу, пользователь вправе ожидать, что в его распоряжении будут соответствующие команды.Конечно, сейчас функции поиска инкапсулированы во многие языки программирования высокого уровня, в связи с этим чтобы найти строчку в небольшом тексте используется встроенная функция. Но если такого рода поиск является ключевой задачей программы, знать принципы организации функций поиска будет полезным. В готовых подпрограммах далеко не всегда все написано лучшим образом. Во-ᴨȇрвых, в стандартных функциях не всегда используются самые эффективные алгоритмы, а во-вторых, вполне возможно, что понадобится изменить стандартное поведение этих функций (например, предусмотреть возможность поиска по шаблону). Наконец, область применения функции поиска не ограничивается одними лишь текстовыми редакторами. Следует отметить использование алгоритмов поиска при индексации страниц поисковым роботом, где актуальность информации напрямую зависит от скорости нахождения ключевых слов в тексте html. Работа простейшего спам-фильтра, заключается в нахождении в тексте письма фраз таких, как «Миллион за час» или «Раскрутка сайта». Это всё говорит об актуальности проблемы поиска.Работа содержит три основных главы. В ᴨȇрвой будут рассмотрены алгоритмы, их теоретическое обоснование, алгоритмическая модель, будет проведена попытка их классификации. Во второй главе будет рассмотрена практическая часть курсовой работы. Реализован программный код поиска подстроки в строке при помощи алгоритма последовательного поиска. В третьей главе работы будут приведены данные о практическом применении алгоритмов. В заключении будет сделан вывод о наиболее эффективном (с временной точки зрения) алгоритме.Глава 1. Теоретические сведения об алгоритмах поиска подстроки в строке1.1. Основные понятияОпределение. Строка (слово) - это последовательность знаков (называемых буквами) из некоторого конечного множества, называемого алфавитом.Определение . Длина строки - количество знаков в строке.Слова обозначаются буквами латинского алфавита, напр. X=x[1]x[2]…x[n] - слово длинной n, где x[i] (i-ая буква слова) принадлежит алфавиту. Lentgh(X)==n - обозначение длины строки.Определение . Слово не содержащее ни одной буквы называется пустым.Пустое слово обычно обозначается буквой L. Length(L)=0.Определение . Слово X называется префиксом слова Y, если есть такое слово Z, что Y=XZ. Причем само слово является префиксом для самого себя (т.к. найдется нулевое слово L, что X=LX.Пример: слово ab является префиксом слова abcfa.Определение . Слово X называется суффиксом слова Y, если есть такое слово Z, что Y=ZX. Аналогично, слово является суффиксом самого себя.Пример: слово bfg является суффиксом слова vsenfbfg.Определение . Слово X называется подстрокой строки Y, если найдутся такие строки Z1 и Z2, что Y=Z1XZ2. При этом Z1 называется левым, а Z2 - правым крылом подстроки. Подстрокой может быть и само слово. Иногда при этом слово X называют вхождением в слово Y. Среди всех вхождений слова X в слово Y, вхождение с наименьшей длиной своего левого крыла называют ᴨȇрвым или главным вхождением. Для обозначения вхождения используют обозначение XY.Пример: слова hrf и fhr является подстроками слова abhrfhr, gfsfdgfro.В программировании понятие сложности алгоритма связано с использованием ресурсов компьютера: насколько много процессорного времени требует программа для своего выполнения, насколько много при этом расходуется память машины? Учет памяти обычно ведется по объему данных и не принимается во внимание память, расходуемая для записи команд программы. Время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой для машин с разной тактовой частотой.Существует две характеристики сложности алгоритмов - временная и емкостная.Временная сложность будет подсчитываться в исполняемых командах: количество арифметических оᴨȇраций, количество сравнений, ᴨȇресылок (в зависимости от алгоритма). Емкостная сложность будет определяться количеством ᴨȇременных, элементов массивов, элементов записей или просто количеством байт.Эффективность алгоритма также будет оцениваться с помощью подсчета времени выполнения алгоритмом конкретно поставленной задачи, т.е. с помощью эксᴨȇримента, подробнее об этом в главе 2 данной работы.1.2. Алгоритм последовательного (прямого) поискаСамый очевидный алгоритм. Обозначеное S - слово, в котором ищется образец X. Пусть m и n - длины слов S и X соответственно. Можно сравнить со словом X все подслова S, которые начинаются с позиций 1,2,...,m-n+1 в слове S; в случае равенства выводится соответствующая позиция. Реализация этого алгоритма представлена в приложении 1.Это не эффективный алгоритм т.к. максимальное, количество сравнений будет равно O((m-n+1)*n+1), хотя большинство из них на самом деле лишние. Оценим скорость работы этого программного кода. В ней присутствуют два цикла (один вложенный), время работы внешнего большей стеᴨȇнью зависит от n, а внутренний в худшем случае делает m оᴨȇраций. Итак, время работы всего алгоритма есть O((n-m+1)m). Для маленьких строк поиск проработает быстро, но если в каком-то многомегабайтном файле будет искаться последовательность длинной 100 Кб, то придется ждать ну очень долго. Впрочем многим хватает и этого. Например, найдя строку aabc и обнаружив несоответствие в четвертом символе (совпало только aab), алгоритм будет продолжать сравнивать строку, начиная со следующего символа, хотя это однозначно не приведет к результату.1.3. Алгоритм РабинаАлгоритм Рабина представляет собой модификацию линейного алгоритма.В слове A, длина которого равна m, ищется образец X длины n. Вырежем "окошечко" размером n оно двигается по входному слову. Совпадает ли слово в "окошечке" с заданным образцом? Фиксируется некоторая числовая функция на словах длины n, тогда задача сводится к сравнению чисел, что, несомненно, быстрее. Если значения этой функции на слове в "окошечке" и на образце различны, то совпадения нет. Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам. Этот алгоритм выполняет линейный проход по строке (n шагов) и линейный проход по всему тексту (m шагов), стало быть, общее время работы есть O(n+m). При этом не учитывается временная сложность вычисления хеш-функции, так как, суть алгоритма в том и заключается, чтобы данная функция была настолько легко вычисляемой, что ее работа не влияла на общую работу алгоритма. Тогда, время работы алгоритма линейно зависит от размера строки и текста, стало быть программа работает быстро. Ведь вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, можно проверять только те, которые «напоминают» образец. Итак, для того, чтобы легко устанавливать явное несоответствие, будет использоваться функция, которая должна:1. Легко вычисляться.2. Как можно лучше различать несовпадающие строки.3. hash( y[ i+1 , i+m ] ) должна легко вычисляться по hash( y[ i , i+m-1 ].Во время поиска х будет сравниваться hash( x ) с hash( y[ i, i+m-1 ] ) для i от 0 до n-m включительно. Если обнаруживается совпадение, то проверяется посимвольно. Реализация этого алгоритма представлена в приложении 2.Пример (удобной для вычисления функции). Заменяются все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге "окошечка" нужно добавить новое число и вычесть "пропавшее".)Однако, проблема в том, что искомая строка может быть длинной, строк в тексте тоже хватает. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть, числа будут большими (порядка D*n, где D - количество различных символов), и работать с ними будет так же неудобно. Но какой интерес работать только с короткими строками и цифрами? Выше рассмотренный алгоритм можно улучшить.Пример (семейства удобных функций). Выбирается некоторое число p (желательно простое) и некоторый вычет x по модулю p. Каждое слово длины n будет рассматриваться как последовательность целых чисел (заменив буквы их кодами). Эти числа будут рассматриваться как коэффициенты многочлена стеᴨȇни n-1 и вычисляется значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и x получается своя функция). Сдвиг "окошечка" на 1 соответствует вычитанию старшего члена, умножению на x и добавлению свободного члена. Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано и к тому же оно является простым, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены (мы предполагаем, что коды всех букв различны - это возможно при p, большем числа букв алфавита). Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, т.е. их разность обращается в 0. Разность есть многочлен стеᴨȇни n-1 и имеет не более n-1 корней. Итак, если n много меньше p, то случайному значению x мало шансов попасть в "неудачную" точку.Строго говоря, время работы всего алгоритма в целом, есть O(m+n+mn/P), mn/P достаточно невелико, так что сложность работы почти линейная. Понятно, что простое число следует выбирать большим, чем больше это число, тем быстрее будет работать программа.Алгоритм Рабина и алгоритм последовательного поиска являются алгоритмами с наименьшими трудозатратами, в связи с этим они годятся для использования при решении некоторого класса задач. Однако эти алгоритмы не являются наиболее оптимальными (хотя бы потому, что иногда выполняют явно бесполезную работу, о чем было сказано выше), в связи с этим будет рассматриваться следующий класс алгоритмов. Эти алгоритмы появились в результате тщательного исследования алгоритма последовательного поиска. Исследователи хотели найти способы более полно использовать информацию, полученную во время сканирования (алгоритм прямого поиска ее просто выбрасывает).1.4.Алгоритм Кнута - Морриса - Пратта (КМП)Метод использует предобработку искомой строки, а именно: на ее основе создается так называемая префикс-функция. Суть этой функции в нахождении для каждой подстроки S[1..i] строки S наибольшей подстроки S[1..j] (j1.5. Алгоритм Бойера - МураАлгоритм Бойера-Мура, разработанный двумя учеными - Бойером и Муром, считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.Простейший вариант алгоритма Бойера-Мура состоит из следующих шагов. На ᴨȇрвом шаге строится таблица смещений для искомого образца. Процесс построения таблицы будет описан ниже. Далее совмещается начало строки и образца и начинается проверка с последнего символа образца. Если заключительный символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. Если же символы совпадают, производится сравнение предпоследнего символа образца и т. д. Если все символы образца совпали с наложенными символами строки, значит нашлась подстрока и поиск окончен. Если же какой-то (не заключительный) символ образца не совпадает с соответствующим символом строки, сдвигается образец на один символ вправо и снова начинается проверку с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки.Величина сдвига в случае несовпадения последнего символа вычисляется исходя из следующих соображений: сдвиг образца должен быть минимальным, таким, чтобы не пропустить вхождение образца в строке. Если данный символ строки встречается в образце, смещается образец таким образом, чтобы символ строки совпал с самым правым вхождением этого символа в образце. Если же образец вообще не содержит этого символа, сдвигается образец на величину, равную его длине, так что ᴨȇрвый символ образца накладывается на следующий за проверявшимся символ строки.Величина смещения для каждого символа образца зависит только от порядка символов в образце, в связи с этим смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа образца.Пример. Пусть есть алфавит из пяти символов: a, b, c, d, e и необходимо найти вхождение образца “abbad” в строке “abeccacbadbabbad”. Следующие схемы иллюстрируют все этапы выполнения алгоритма. Таблица смещений будет выглядеть так.Начало поиска.Последний символ образца не совпадает с наложенным символом строки. Сдвигается образец вправо на 5 позиций:Три символа образца совпали, а четвертый - нет. Сдвигается образец вправо на одну позицию:Последний символ снова не совпадает с символом строки. В соответствии с таблицей смещений сдвигается образец на 2 позиции:Еще раз сдвигается образец на 2 позиции:Теᴨȇрь, в соответствии с таблицей, сдвигается образец на одну позицию, и получается искомое вхождение образца:Прежде всего следует определить тип данных «таблица смещений». Для кодовой таблицы, состоящей из 256 символов, определение этого типа будет выглядеть так:TypeTBMTable = Array [0..255] of Integer;Реализация процедуры, вычисляющая таблицу смещений для образца p, представлена в приложении 5.Теᴨȇрь пишется функция, осуществляющая поиск (см. Приложение 6).Параметр StartPos позволяет указать позицию в строке s, с которой следует начинать поиск. Это может быть полезно в том случае, если необходимо найти все вхождения p в s. Для поиска с самого начала строки следует задать StartPos равным 1. Если результат поиска не равен нулю, то для того, чтобы найти следующее вхождение p в s, нужно задать StartPos равным значению «предыдущий результат плюс длина образца».Глава 2. Практическая часть.Дан некоторый текст, в котором следует найти фрагмент этого текста.Данную задачу можно интерпретировать как поиск подстроки в строке.Эту задачу я реализовал при помощи алгоритма последовательного (прямого) поиска. Программный код задачи реализовал на языке программирования Turbo Pascal 7.1 и он представлен в приложении 7. Описание работы программы.После запуска программа запрашивает ввод текста:Например, введём следующий текст: ”алгоритм рабина представляет собой модификацию линейного алгоритма.”Далее программа запрашивает ввод строки(подстроки) для поиска:Например, вводим фрагмент текста: ”алгоритм”После ввода, программа ищет строку в тексте, если строка существует то программа выводит текст на экран, выделяет строку красным цветом и выдает с какого символа начинается строка:Если фрагмента нет в тексте, то программа выдаст сообщение о том, что данной строки в тексте не существует:Глава 3. Анализ алгоритмовВ курсовой работе я рассмотрел несколько алгоритмов. Была проведена оценка их временной и емкостной сложности. Эксᴨȇриментальный анализ состоял в измерении времени, за которое алгоритм выполняет конкретно поставленную задачу.Задача: Имеется несколько текстовых файлов, содержащих 10000 записей вида:§ строка§ подстрока (имеющаяся в данной строке)§ место вхождения§ длина подстроки,причем с разными максимальными длинами строк и подстрок.Алфавит кириллицы содержит 32 буквы, в связи с этим длина строки будет не более 10, 100, 250 символов.Проводится поиск подстрок в строках для каждого из алгоритмов и измеряется время работы программы. При этом будет учитываться следующее:· строки предварительно загружаем в оᴨȇративную память (в виде массива), причем время считывания в массив не учитывается. Предобработка (создание таблиц ᴨȇрехода) входит в общее время.· каждый алгоритм запускается 5 раз, время выбирается наименьшее.Эксᴨȇримент проходил на ПК:Процессор Intel Pentium IV 2,66Ггц1024 Мб ОЗУКомпилятор Turbo Pascal 7.1Фрагмент кода тестируемой программы приводится в Приложении 8.Такой замер времени даст приблизительные результаты, так как напрямую зависит от характеристик и загрузки процессора. В связи с этим во время проведения эксᴨȇримента, отключались все сторонние и фоновые приложения, которые не влияют на работу программы. При запуске одной и той же задачи можно получить разное время, в связи с этим совершается несколько запусков, из котоҏыҳ выбирается наилучший результат.Эксᴨȇримент проводился для четырех алгоритмов - представителей классов алгоритмов. Так как все алгоритмы ставились в одинаковые условия, то можно провести их сравнительный анализ. Заметим, что данный анализ применим только для данных параметров поиска, и при иных условиях может отличаться.Результаты эксᴨȇримента занесены в таблицу 1.Алгоритм | Время выполнения (мс) | |||
Длина ?10 | Длина ?100 | Длина ?250 | ||
Послед. Поиск | 15 | 93 | 234 | |
Алгоритм Рабина | 15 | 63 | 93 | |
КМП | 5 | 30 | 50 | |
БМ | 31 | 31 | 32 |
3
3
Приложение 3Алгоритм Кнута-Морриса-ПраттаНахождение наибольшего искомого префикса.3
Приложение 4Реализация алгоритма Кнута-Морриса-Пратта3
Приложение 5Алгоритм Бойера-МураРеализация процедуры, вычисляющая таблицу смещений для образца p.3
Приложение 6Алгоритм Бойера-МураФункция, осуществляющая поиск.3
Приложение 7Реализация программного кода3
Приложение 8Фрагмент кода тестируемой программы3
Приложение 9Общие результаты с анализов рассмотренных алгоритмовПримечания | Алгоритмы, основанные на алгоритме последовательного поиска | Малые трудозатраты на программу, малая эффективность | Алгоритм Кнута-Морриса-Пратта | Универсальный алгоритм, если неизвестна длина образца | Алгоритм Бойера-Мура | Алгоритмы этой группы наиболее эффективны в обычных ситуациях. Быстродействие повышается при увеличении образца или алфавита. | ||
Время работы (мс) при длине строки ?250 | 234 | 93 | 31 | 32 | ||||
Затраты памяти | нет | нет | O(m) | O(m+s) | ||||
Худшее время поиска | O((m-n+1)*n+1) | O((m-n+1)*n+1) | O(n+m) | O(n*m) | ||||
Среднее время поиска | O((m-n+1)*n+1)/2 | O(n+m) | O(n+m) | O(n+m) | ||||
Время на пред. обработку | нет | нет | O(m) | O(m+s) | ||||
Алгоритм | Алгоритм прямого поиска | Алгоритм Рабина | КМП | БМ |
referatwork.ru
Лабораторная работа 8.
Тема: Алгоритмы поиска и выборки.
Задания:
1. Написать программу реализующую алгоритм последовательного поиск целевого значения из выборки N чисел (использовать любой язык программирования).
2. Написать программу реализующую алгоритм двоичного поиска целевого значения из выборки N чисел (использовать любой язык программирования).
3. Провести анализ наихудшего и среднего случаев.
4. Оформить отчет в MSWord и показать работающую программу преподавателю.
Теоретический минимум.
Алгоритмы поиска и выборки
Поиск необходимой информации в списке — одна из фундаментальныхзадач теоретического программирования. При обсуждении алгоритмов поиска мы предполагаем, что информация содержится в записях, составляющих некоторый список, который представляет собой массив данных в программе. Записи, или элементы списка, идут в массиве последовательно и между ними нет промежутков. Номера записей в списке идут от 1 до N — полного числа записей. В принципе записи могут быть составлены из полей, однако нас будут интересовать значения лишь одного из этих полей, называемого ключом. Списки могут быть не отсортированными или отсортированными по значению ключевого поля. В не отсортированном списке порядок записей случаен, а в отсортированном они идут в порядке возрастания ключа.
Поиск нужной записи в не отсортированном списке сводится к просмотру всего списка до того, как запись будет найдена. Это простейший из алгоритмов поиска. Мы увидим, что этот алгоритм не очень эффективен, однако он работает на произвольном списке.
В отсортированном списке возможен также двоичный поиск. Двоичный поиск использует преимущества, предоставляемые имеющимся упорядочиванием, для того, чтобы отбрасывать за одно сравнение больше одного элемента. В результате поиск становится более эффективным.
С поиском конкретного значения связана задача выборки, в которой требуется найти элемент, удовлетворяющий некоторым условиям. Скажем, нам может понадобиться пятый по величине элемент, седьмой с конца или элемент со средним значением. Мы обсудим два подхода к этой задаче.
1. Последовательный поиск
В алгоритмах поиска нас интересует процесс просмотра списка в поисках некоторого конкретного элемента, называемого целевым. При последовательном поиске мы всегда будем предполагать, хотя в этом и нет особой необходимости, что список не отсортирован, поскольку некоторые алгоритмы на отсортированных списках показывают лучшую производительность. Обычно поиск производится не просто для проверки того, что нужный элемент в списке имеется, но и для того, чтобы получить данные, относящиеся к этому значению ключа. Например, ключевое значение может быть номером сотрудника или порядковым номером, или любым другим уникальным идентификатором. После того, как нужный ключ найден, программа может, скажем, частично изменить связанные с ним данные или просто вывести всю запись. Во всяком случае, перед алгоритмом поиска стоит важная задача определения местонахождения ключа. Поэтому алгоритмы поиска возвращают индекс записи, содержащей нужный ключ. Если ключевое значение не найдено, то алгоритм поиска обычно возвращает значение индекса, превышающее верхнюю границу массива. Для наших целей мы будем предполагать, что элементы списка имеют номера от 1 до N . Это позволит нам возвращать 0 в случае, если целевой элемент отсутствует в списке. Для простоты мы предполагаем, что ключевые значения не повторяются.
Алгоритм последовательного поиска последовательно просматривает по одному элементу списка, начиная с первого, до тех пор, пока не найдет целевой элемент. Очевидно, что чем дальше в списке находится конкретное значение ключа, тем больше времени уйдет на его поиск. Это следует помнить при анализе алгоритма последовательного поиска.
Вот как выглядит полный алгоритм последовательного поиска.
SequentialSearch(list.target,N) listсписок для просмотра
target целевое значение N число элементов в списке
for i=l to N do
if (target=list[i])
return i
end if
end for
return 0
Анализ наихудшего случая
У алгоритма последовательного поиска два наихудших случая. В первом случае целевой элемент стоит в списке последним. Во втором его вовсе нет в списке. Посмотрим, сколько сравнений выполняется в каждом из этих случаев. Мы предположили, что все ключевые значения в списке уникальны, и поэтому если совпадение произошло в последней записи, то все предшествующие сравнения были неудачными. Однако алгоритм проделывает все эти сравнения пока не дойдет до последнего элемента. В результате будет проделано N сравнений, где N — число элементов в списке.
Чтобы проверить, что целевое значение в списке отсутствует, его придется сравнить со всеми элементами списка. Если мы пропустим какой-то элемент, то не сможем выяснить, отсутствует ли целевое значение в списке вообще или оно содержится в каком-то из пропущенных элементов. Это означает, что для выяснения того, что ни один из элементов не является целевым, нам потребуется N сравнений.
Так что N сравнений необходимо как для того, чтобы найти значение, содержащееся в последнем элементе списка, так и для того, чтобы выяснить, что целевого значения в списке нет. Ясно, что N дает верхнюю границу сложности любого алгоритма поиска, поскольку, если сравнений больше N , то это означает, что сравнение с каким-то элементом выполнялось по крайней мере дважды, а значит была проделана лишняя работа, и алгоритм можно улучшить.
Между понятиями верхней границы сложности и сложности в наихудшем случае есть разница. Верхняя граница присуща самой задаче, а понятие наихудшего случая относится к решающему ее конкретному алгоритму.
Анализ среднего случая
Для алгоритмов поиска возможны два средних случая. В первом предполагается, что поиск всегда завершается успешно, во втором — что иногда целевое значение в списке отсутствует.
Если целевое значение содержится в списке, то оно может занимать одно из N возможных положений: оно может быть первым, вторым, третьим, четвертым и так далее. Мы будем предполагать все эти положения равновероятными, т.е. вероятность встретить каждое из них равна 1/N.
Прежде, чем читать дальше, ответьте на следующие вопросы.
• • Сколько сравнений требуется, если искомый элемент стоит в спи ске первым?
• • А если вторым?
• • А если третьим?
• • А если последним из N элементов?
Если Вы внимательно посмотрели на алгоритм, то Вам несложно определить, что ответы будут выглядеть 1, 2, 3 и N соответственно. Это означает, что для каждого из N случаев число сравнений совпадает с номером искомого элемента. В результате для сложности в среднем случае мы получаем равенство
Если мы допускаем, что целевого значения может не оказаться в списке, то количество возможностей возрастает до N + 1.
Как мы уже видели, при отсутствии элемента в списке его поиск требует N сравнений. Если предположить, что все N + 1 возможностей равновероятны, то получится следующая выкладка:
(Когда N становится очень большим, значение 1/( N + 1) оказывается близким к 0.)
Видно, что допущение о возможности отсутствия элемента в списке увеличивает сложность среднего случая лишь на 1/2. Ясно, что по сравнению с длиной списка, которая может быть очень велика, эта величина пренебрежимо мала.
2. Двоичный поиск
При сравнении целевого значения со средним элементом отсортированного списка возможен один из трех результатов: значения равны, целевое значение меньше элемента списка, либо целевое значение больше элемента списка. В первом, и наилучшем, случае поиск завершен. В остальных двух случаях мы можем отбросить половину списка.
Когда целевое значение меньше среднего элемента, мы знаем, что если оно имеется в списке, то находится перед этим средним элементом. Когда же оно больше среднего элемента, мы знаем, что если оно имеется в списке, то находится после этого среднего элемента. Этого достаточно, чтобы мы могли одним сравнением отбросить половину списка. При повторении этой процедуры мы сможем отбросить половину оставшейся части списка. В результате мы приходим к следующему алгоритму
BinarySearch (list .target ,N ) list список для просмотра target целевое значение N число элементов в списке
start=l
end=N
while start<=end do
middle=(start+end)/2
select(Compare(list[middle].target)) from
case -1: start=middle+l
case 0: return middle
case 1: end=middle-l
end select
end while
return 0
В этом алгоритме переменной start присваивается значение, на 1 большее, чем значение переменной middle, если целевое значение превышает значение найденного среднего элемента. Если целевое значение меньше значения найденного среднего элемента, то переменной end присваивается значение, на 1 меньше, чем значение переменной middle. Сдвиг на 1 объясняется тем, что в результате сравнения мы знаем, что среднее значение не является искомым, и поэтому его можно исключить из рассмотрения.
Всегда ли цикл останавливается? Если целое значение найдено, то ответ, разумеется, утвердительный, поскольку выполняется оператор return. Если нужное значение не найдено, то на каждой итерации цикла либо возрастает значение переменной start, либо уменьшается значение переменойend. Это означает, что их значения постепенно сближаются. В какой-то момент эти два значения становятся равными, и цикл выполняется еще один раз при соблюдении равенства start =end =middle. После этого прохода (если элемент с этим индексом не является искомым) либо переменная start окажется на 1 больше, чем end и middle, либо наоборот, переменная end окажется на 1 меньше, чем start и middle. В обоих случаях условие цикла while ложным, и цикл больше выполнятся не будет. Поэтому выполнение цикла завершается всегда.
Возвращает ли этот алгоритм правильный результат? Если целевое значение найдено, то ответ безусловно утвердительный, поскольку выполнен оператор return. Если же средний элемент оставшейся части списка не подходит, то на каждом подходе цикла происходит исключение половины оставшихся элементов, поскольку все они либо чересчур велики, чересчур малы. Ранее мы говорили, что в результате мы придем к единственному элементу, который следует проверить. Если это нужный нам ключ то будет возвращено значение переменной middle. Если же значение ключа отлично от искомого, то значение переменной start превысит значение end или наоборот, значение переменной end станет меньше значения start. Если бы целевое значение содержалось в списке, то оно было бы меньше или больше значения элемента middle. Однако значения переменных start и end показывают, что предыдущие сравнения исключили все остальные возможности, и поэтому целевое значение отсутствует в списке. Значит цикл завершит работу, а возращенное значение будет равно нулю, что указывает на неудачу поиска. Таким образом, алгоритм возвращает верный ответ.
Поскольку алгоритм всякий раз делит список пополам, мы будем предполагать при анализе, что N=2k -1 для некоторого k. Если это так, то сколько элементов останется при втором проходе? А третьем? Вообще говоря, ясно, что если на некотором подходе цикл имеет дело со списком из 2j -1 элементов, то в первой половине списка 2j-1 -1 элементов, один элемент в середине, и 2j-1 -1 элементов во второй половине списка. Поэтому к следующему проходу остаётся 2j-1 -1 элемент (при ). Это предложение позволяет упростить последующий анализ, но необходимости в нем нет.
Анализ наихудшего случая.
В предыдущем абзаце мы показали, что степень двойки в длине оставшейся части списка при всяком проходе цикла уменьшится на 1, а также, что последняя итерация цикла производится, кода размер оставшейся части становится равным 1, а это происходит при j=1 (так как 21 -1=1). Это означает, что при N=2k -1 число проходов не превышает k. Решая последние уравнение относительно k, мы заключаем, что в наихудшем случае число проходов равно k=log2 (N+1).
В анализе может помочь и дерево для процесса поиска. В узлах дерева решение стоят элементы, которые проверяются на соответствующем проходе. Элементы, проверка которых будет осуществляться в том случае, если целевое значение меньше текущего элемента, а сравниваемые в случае, если целевое значение больше текущего – в правом поддереве. Дерево решение для списка из 7 элементов изображено на рисунке1. В общем случае дерево относительно сбалансировано, поскольку мы всегда выбираем середину различных частей списка. Поэтому для подсчета числа сравнений мы можем воспользоваться формулами для бинарных деревьев.
Поскольку мы предполагаем, что N=2k -1, соответствующие дерево решение будет всегда полным. В нем будет k уровней, где k=log2 (N+1). Мы делаем по одному сравнению на каждом уровне, поэтому полное число сравнений не превосходит log2 (N+1).
Рис. 1. Дерево решений для поиска в списке из семи элементов
Анализ среднего случая (изучить самостоятельно)
2.3. Выборка
Иногда нам нужен элемент из списка, обладающий некоторыми специальными свойствами, а не имеющий некоторое конкретное значение. Другими словами, вместо записи с некоторым конкретным значением поля нас интересует, скажем, запись с наибольшим, наименьшим или средним значением этого поля. В более общем случае нас может интересовать запись с К-ыы по величине значением поля.
Один из способов найти такую запись состоит в том, чтобы отсортировать список в порядке убывания; тогда запись с К-ыш по величине значением окажется на К-оы месте. На это уйдет гораздо больше сил, чем необходимо: значения, меньшие искомого, нас, на самом деле, не интересуют. Может пригодиться следующий подход: мы находим наибольшее значение в списке и помещаем его в конец списка. Затем мы можем найти наибольшее значение в оставшейся части списка, исключая уже найденное. В результате мы получаем второе по величине значение списка, которое можно поместить на второе с конца место в списке. Повторив эту процедуру К раз, мы найдем К-ое по величине значение. В результате мы приходим к алгоритму
FindKthLargest(list,K,N)
list список для просмотра
N число элементов в списке
К порядковый номер по величине требуемого элемента
for i=l to К do
largest=list[1]
largestLocation=1
for j=2 to N-(i-l) do
if list [j]>largest then
largest=list[j] largestLocation=j end if
end for
Swap(list[N-(i-l)],list[largestLocation])
end for
return largest
Какова сложность этого алгоритма? На каждом проходе мы присваиваем переменной largest значение первого элемента списка, а затем сравниваем эту переменную со всеми остальными элементами. При первом проходе мы делаем N — 1 сравнение, на втором — на одно сравнение меньше. На К- омпроходе мы делаем N — К сравнений. Поэтому для поиска К-ого по величине элемента нам потребуется
сравнений, что по порядку величины равно O (KN ). Следует заметить также, что если К больше, чем N /2, то поиск лучше начинать с конца списка. Для значений К близких к 1 или к N этот алгоритм довольно эффективен, однако для поиска значений из середины списка есть и более эффективные алгоритмы.
Поскольку нам нужно лишь К-ое по величине значение, точное местоположение больших К—\ элементов нас на самом деле не интересует, нам достаточно знать, что они больше искомого. Для всякого элемента из списка весь список распадается на две части: элементы, большие взятого, и меньшие элементы. Если переупорядочить элементы в списке так, чтобы все большие шли за выбранным, а все меньшие — перед ним, и при этом выбранный элемент окажется на Р-ом месте, то мы будем знать, что он Р-ый по величине. Такое переупорядочивание потребует сравнения выбранного элемента со всеми остальными, т.е. N — 1 сравнений. Если нам повезло и Р = К, то работа закончена. Если К < Р, то нам нужно некоторое большее значение, и проделанную процедуру можно повторить со второй частью списка. Если К > Р, то нам нужно меньшее значение, и мы можем воспользоваться первой частью списка; при этом, однако, К следует уменьшить на число откинутых во второй части элементов. В результате мы приходим к следующему рекурсивному алгоритму.
KthLargestRecursive(list.start,end, К)
list список для просмотра
start индекс первого рассматриваемого элемента
end индекс последнего рассматриваемого элемента
К порядковый номер по величине требуемого элемента
if start< end then
Partitiondist, start,end.middle) if middle=K then
return list[middle] else
if K<middle then
return KthLargestRecursive(list,middle+1,end,K) else
return KthLargestRecursive(list,start,middle-l,K-middle)
end if
end if
end if
Если предположить, что в среднем при разбиении список будет де литься на две более или менее равные половины, то число сравнений будет приблизительно равно
N + N/2 + N/4 + N/8+…+1, т.е. 2N. Поэтому сложность алгоритма линейна и не зависит от К.
Литература:
1. Дж. Макконелл Анализ алгоритмов. Вводный курс
2. Д.Э. Кнут Искусство программирования. Том 3.
www.ronl.ru
Тема: Алгоритмы поиска и выборки.
Задания:
1. Написать программу реализующую алгоритм последовательного поиск целевого значения из выборки N чисел (использовать любой язык программирования).
2. Написать программу реализующую алгоритм двоичного поиска целевого значения из выборки N чисел (использовать любой язык программирования).
3. Провести анализ наихудшего и среднего случаев.
4. Оформить отчет в MS Word и показать работающую программу преподавателю.
Теоретический минимум. Алгоритмы поиска и выборки
Поиск необходимой информации в списке — одна из фундаментальных задач теоретического программирования. При обсуждении алгоритмов поиска мы предполагаем, что информация содержится в записях, составляющих некоторый список, который представляет собой массив данных в программе. Записи, или элементы списка, идут в массиве последовательно и между ними нет промежутков. Номера записей в списке идут от 1 до N — полного числа записей. В принципе записи могут быть составлены из полей, однако нас будут интересовать значения лишь одного из этих полей, называемого ключом. Списки могут быть не отсортированными или отсортированными по значению ключевого поля. В не отсортированном списке порядок записей случаен, а в отсортированном они идут в порядке возрастания ключа.
Поиск нужной записи в не отсортированном списке сводится к просмотру всего списка до того, как запись будет найдена. Это простейший из алгоритмов поиска. Мы увидим, что этот алгоритм не очень эффективен, однако он работает на произвольном списке.
В отсортированном списке возможен также двоичный поиск. Двоичный поиск использует преимущества, предоставляемые имеющимся упорядочиванием, для того, чтобы отбрасывать за одно сравнение больше одного элемента. В результате поиск становится более эффективным.
С поиском конкретного значения связана задача выборки, в которой требуется найти элемент, удовлетворяющий некоторым условиям. Скажем, нам может понадобиться пятый по величине элемент, седьмой с конца или элемент со средним значением. Мы обсудим два подхода к этой задаче.
1. Последовательный поиск
В алгоритмах поиска нас интересует процесс просмотра списка в поисках некоторого конкретного элемента, называемого целевым. При последовательном поиске мы всегда будем предполагать, хотя в этом и нет особой необходимости, что список не отсортирован, поскольку некоторые алгоритмы на отсортированных списках показывают лучшую производительность. Обычно поиск производится не просто для проверки того, что нужный элемент в списке имеется, но и для того, чтобы получить данные, относящиеся к этому значению ключа. Например, ключевое значение может быть номером сотрудника или порядковым номером, или любым другим уникальным идентификатором. После того, как нужный ключ найден, программа может, скажем, частично изменить связанные с ним данные или просто вывести всю запись. Во всяком случае, перед алгоритмом поиска стоит важная задача определения местонахождения ключа. Поэтому алгоритмы поиска возвращают индекс записи, содержащей нужный ключ. Если ключевое значение не найдено, то алгоритм поиска обычно возвращает значение индекса, превышающее верхнюю границу массива. Для наших целей мы будем предполагать, что элементы списка имеют номера от 1 до N. Это позволит нам возвращать 0 в случае, если целевой элемент отсутствует в списке. Для простоты мы предполагаем, что ключевые значения не повторяются.
Алгоритм последовательного поиска последовательно просматривает по одному элементу списка, начиная с первого, до тех пор, пока не найдет целевой элемент. Очевидно, что чем дальше в списке находится конкретное значение ключа, тем больше времени уйдет на его поиск. Это следует помнить при анализе алгоритма последовательного поиска.
Вот как выглядит полный алгоритм последовательного поиска.
SequentialSearch(list.target,N) list список для просмотра
target целевое значение N число элементов в списке
for i=l to N do
if (target=list[i])
return i
end if
end for
return 0
Анализ наихудшего случая
У алгоритма последовательного поиска два наихудших случая. В первом случае целевой элемент стоит в списке последним. Во втором его вовсе нет в списке. Посмотрим, сколько сравнений выполняется в каждом из этих случаев. Мы предположили, что все ключевые значения в списке уникальны, и поэтому если совпадение произошло в последней записи, то все предшествующие сравнения были неудачными. Однако алгоритм проделывает все эти сравнения пока не дойдет до последнего элемента. В результате будет проделано N сравнений, где N — число элементов в списке.
Чтобы проверить, что целевое значение в списке отсутствует, его придется сравнить со всеми элементами списка. Если мы пропустим какой-то элемент, то не сможем выяснить, отсутствует ли целевое значение в списке вообще или оно содержится в каком-то из пропущенных элементов. Это означает, что для выяснения того, что ни один из элементов не является целевым, нам потребуется N сравнений.
Так что N сравнений необходимо как для того, чтобы найти значение, содержащееся в последнем элементе списка, так и для того, чтобы выяснить, что целевого значения в списке нет. Ясно, что N дает верхнюю границу сложности любого алгоритма поиска, поскольку, если сравнений больше N, то это означает, что сравнение с каким-то элементом выполнялось по крайней мере дважды, а значит была проделана лишняя работа, и алгоритм можно улучшить.
Между понятиями верхней границы сложности и сложности в наихудшем случае есть разница. Верхняя граница присуща самой задаче, а понятие наихудшего случая относится к решающему ее конкретному алгоритму.
Анализ среднего случая
Для алгоритмов поиска возможны два средних случая. В первом предполагается, что поиск всегда завершается успешно, во втором — что иногда целевое значение в списке отсутствует.
Если целевое значение содержится в списке, то оно может занимать одно из N возможных положений: оно может быть первым, вторым, третьим, четвертым и так далее. Мы будем предполагать все эти положения равновероятными, т.е. вероятность встретить каждое из них равна 1/N.
Прежде, чем читать дальше, ответьте на следующие вопросы.
Если мы допускаем, что целевого значения может не оказаться в списке, то количество возможностей возрастает до N + 1.
Как мы уже видели, при отсутствии элемента в списке его поиск требует N сравнений. Если предположить, что все N + 1 возможностей равновероятны, то получится следующая выкладка:
(Когда N становится очень большим, значение 1/(N + 1) оказывается близким к 0.)
Видно, что допущение о возможности отсутствия элемента в списке увеличивает сложность среднего случая лишь на 1/2. Ясно, что по сравнению с длиной списка, которая может быть очень велика, эта величина пренебрежимо мала.
2. Двоичный поиск
При сравнении целевого значения со средним элементом отсортированного списка возможен один из трех результатов: значения равны, целевое значение меньше элемента списка, либо целевое значение больше элемента списка. В первом, и наилучшем, случае поиск завершен. В остальных двух случаях мы можем отбросить половину списка.
Когда целевое значение меньше среднего элемента, мы знаем, что если оно имеется в списке, то находится перед этим средним элементом. Когда же оно больше среднего элемента, мы знаем, что если оно имеется в списке, то находится после этого среднего элемента. Этого достаточно, чтобы мы могли одним сравнением отбросить половину списка. При повторении этой процедуры мы сможем отбросить половину оставшейся части списка. В результате мы приходим к следующему алгоритму
BinarySearch(list.target,N) list список для просмотра target целевое значение N число элементов в списке
start=l
end=N
while start
middle=(start+end)/2
select(Compare(list[middle].target)) from
case -1: start=middle+l
case 0: return middle
case 1: end=middle-l
end select
end while
return 0
В этом алгоритме переменной start присваивается значение, на 1 большее, чем значение переменной middle, если целевое значение превышает значение найденного среднего элемента. Если целевое значение меньше значения найденного среднего элемента, то переменной end присваивается значение, на 1 меньше, чем значение переменной middle. Сдвиг на 1 объясняется тем, что в результате сравнения мы знаем, что среднее значение не является искомым, и поэтому его можно исключить из рассмотрения.
Всегда ли цикл останавливается? Если целое значение найдено, то ответ, разумеется, утвердительный, поскольку выполняется оператор return. Если нужное значение не найдено, то на каждой итерации цикла либо возрастает значение переменной start, либо уменьшается значение переменой end. Это означает, что их значения постепенно сближаются. В какой-то момент эти два значения становятся равными, и цикл выполняется еще один раз при соблюдении равенства start=end=middle. После этого прохода (если элемент с этим индексом не является искомым) либо переменная start окажется на 1 больше, чем end и middle, либо наоборот, переменная end окажется на 1 меньше, чем start и middle. В обоих случаях условие цикла while ложным, и цикл больше выполнятся не будет. Поэтому выполнение цикла завершается всегда.
Возвращает ли этот алгоритм правильный результат? Если целевое значение найдено, то ответ безусловно утвердительный, поскольку выполнен оператор return. Если же средний элемент оставшейся части списка не подходит, то на каждом подходе цикла происходит исключение половины оставшихся элементов, поскольку все они либо чересчур велики, чересчур малы. Ранее мы говорили, что в результате мы придем к единственному элементу, который следует проверить. Если это нужный нам ключ то будет возвращено значение переменной middle. Если же значение ключа отлично от искомого, то значение переменной start превысит значение end или наоборот, значение переменной end станет меньше значения start. Если бы целевое значение содержалось в списке, то оно было бы меньше или больше значения элемента middle. Однако значения переменных start и end показывают, что предыдущие сравнения исключили все остальные возможности, и поэтому целевое значение отсутствует в списке. Значит цикл завершит работу, а возращенное значение будет равно нулю, что указывает на неудачу поиска. Таким образом, алгоритм возвращает верный ответ.
Поскольку алгоритм всякий раз делит список пополам, мы будем предполагать при анализе, что N=2k-1 для некоторого k. Если это так, то сколько элементов останется при втором проходе? А третьем? Вообще говоря, ясно, что если на некотором подходе цикл имеет дело со списком из 2j-1 элементов, то в первой половине списка 2j-1-1 элементов, один элемент в середине, и 2j-1-1 элементов во второй половине списка. Поэтому к следующему проходу остаётся 2j-1-1 элемент (при ). Это предложение позволяет упростить последующий анализ, но необходимости в нем нет.
Анализ наихудшего случая.
В предыдущем абзаце мы показали, что степень двойки в длине оставшейся части списка при всяком проходе цикла уменьшится на 1, а также, что последняя итерация цикла производится, кода размер оставшейся части становится равным 1, а это происходит при j=1 (так как 21-1=1). Это означает, что при N=2k-1 число проходов не превышает k. Решая последние уравнение относительно k, мы заключаем, что в наихудшем случае число проходов равно k=log2(N+1).
В анализе может помочь и дерево для процесса поиска. В узлах дерева решение стоят элементы, которые проверяются на соответствующем проходе. Элементы, проверка которых будет осуществляться в том случае, если целевое значение меньше текущего элемента, а сравниваемые в случае, если целевое значение больше текущего – в правом поддереве. Дерево решение для списка из 7 элементов изображено на рисунке1. В общем случае дерево относительно сбалансировано, поскольку мы всегда выбираем середину различных частей списка. Поэтому для подсчета числа сравнений мы можем воспользоваться формулами для бинарных деревьев.
Поскольку мы предполагаем, что N=2k-1, соответствующие дерево решение будет всегда полным. В нем будет k уровней, где k=log2(N+1). Мы делаем по одному сравнению на каждом уровне, поэтому полное число сравнений не превосходит log2(N+1).
Рис. 1. Дерево решений для поиска в списке из семи элементов
Анализ среднего случая (изучить самостоятельно)
2.3. Выборка
Иногда нам нужен элемент из списка, обладающий некоторыми специальными свойствами, а не имеющий некоторое конкретное значение. Другими словами, вместо записи с некоторым конкретным значением поля нас интересует, скажем, запись с наибольшим, наименьшим или средним значением этого поля. В более общем случае нас может интересовать запись с К-ыы по величине значением поля.
Один из способов найти такую запись состоит в том, чтобы отсортировать список в порядке убывания; тогда запись с К-ыш по величине значением окажется на К-оы месте. На это уйдет гораздо больше сил, чем необходимо: значения, меньшие искомого, нас, на самом деле, не интересуют. Может пригодиться следующий подход: мы находим наибольшее значение в списке и помещаем его в конец списка. Затем мы можем найти наибольшее значение в оставшейся части списка, исключая уже найденное. В результате мы получаем второе по величине значение списка, которое можно поместить на второе с конца место в списке. Повторив эту процедуру К раз, мы найдем К-ое по величине значение. В результате мы приходим к алгоритму
FindKthLargest(list,K,N)
list список для просмотра
N число элементов в списке
К порядковый номер по величине требуемого элемента
for i=l to К do
largest=list[1]
largestLocation=1
for j=2 to N-(i-l) do
if list [j]>largest then
largest=list[j] largestLocation=j end if
end for
Swap(list[N-(i-l)],list[largestLocation])
end for
return largest
Какова сложность этого алгоритма? На каждом проходе мы присваиваем переменной largest значение первого элемента списка, а затем сравниваем эту переменную со всеми остальными элементами. При первом проходе мы делаем N — 1 сравнение, на втором — на одно сравнение меньше. На К-ом проходе мы делаем N — К сравнений. Поэтому для поиска К-ого по величине элемента нам потребуется
сравнений, что по порядку величины равно O(KN). Следует заметить также, что если К больше, чем N/2, то поиск лучше начинать с конца списка. Для значений К близких к 1 или к N этот алгоритм довольно эффективен, однако для поиска значений из середины списка есть и более эффективные алгоритмы.
Поскольку нам нужно лишь К-ое по величине значение, точное местоположение больших К—\ элементов нас на самом деле не интересует, нам достаточно знать, что они больше искомого. Для всякого элемента из списка весь список распадается на две части: элементы, большие взятого, и меньшие элементы. Если переупорядочить элементы в списке так, чтобы все большие шли за выбранным, а все меньшие — перед ним, и при этом выбранный элемент окажется на Р-ом месте, то мы будем знать, что он Р-ый по величине. Такое переупорядочивание потребует сравнения выбранного элемента со всеми остальными, т.е. N — 1 сравнений. Если нам повезло и Р = К, то работа закончена. Если К то нам нужно некоторое большее значение, и проделанную процедуру можно повторить со второй частью списка. Если К > Р, то нам нужно меньшее значение, и мы можем воспользоваться первой частью списка; при этом, однако, К следует уменьшить на число откинутых во второй части элементов. В результате мы приходим к следующему рекурсивному алгоритму.
KthLargestRecursive(list.start,end,К)
list список для просмотра
start индекс первого рассматриваемого элемента
end индекс последнего рассматриваемого элемента
К порядковый номер по величине требуемого элемента
if start
Partitiondist, start,end.middle) if middle=K then
return list[middle] else
if K
return KthLargestRecursive(list,middle+1,end,K) else
return KthLargestRecursive(list,start,middle-l,K-middle)
end if
end if
end if
Если предположить, что в среднем при разбиении список будет де литься на две более или менее равные половины, то число сравнений будет приблизительно равно
N + N/2 + N/4 + N/8+…+1 , т.е. 2N. Поэтому сложность алгоритма линейна и не зависит от К.
Литература:
www.coolreferat.com
