Алгоритмы поиска и выборки (стр. 2 из 2)

Возвращает ли этот алгоритм правильный результат? Если целевое значение найдено, то ответ безусловно утвердительный, поскольку выполнен оператор return. Если же средний элемент оставшейся части списка не подходит, то на каждом подходе цикла происходит исключение половины оставшихся элементов, поскольку все они либо чересчур велики, чересчур малы. Ранее мы говорили, что в результате мы придем к единственному элементу, который следует проверить. Если это нужный нам ключ то будет возвращено значение переменной middle. Если же значение ключа отлично от искомого, то значение переменной start превысит значение end или наоборот, значение переменной end станет меньше значения start. Если бы целевое значение содержалось в списке, то оно было бы меньше или больше значения элемента middle. Однако значения переменных start и end показывают, что предыдущие сравнения исключили все остальные возможности, и поэтому целевое значение отсутствует в списке. Значит цикл завершит работу, а возращенное значение будет равно нулю, что указывает на неудачу поиска. Таким образом, алгоритм возвращает верный ответ.

Поскольку алгоритм всякий раз делит список пополам, мы будем предполагать при анализе, что N=2^k-1 для некоторого k. Если это так, то сколько элементов останется при втором проходе? А третьем? Вообще говоря, ясно, что если на некотором подходе цикл имеет дело со списком из 2^j-1 элементов, то в первой половине списка 2^j-1-1 элементов, один элемент в середине, и 2^j-1-1 элементов во второй половине списка. Поэтому к следующему проходу остаётся 2^j-1-1 элемент (при

). Это предложение позволяет упростить последующий анализ, но необходимости в нем нет.

Анализ наихудшего случая.

В предыдущем абзаце мы показали, что степень двойки в длине оставшейся части списка при всяком проходе цикла уменьшится на 1, а также, что последняя итерация цикла производится, кода размер оставшейся части становится равным 1, а это происходит при j=1 (так как 2¹-1=1). Это означает, что при N=2^k-1 число проходов не превышает k. Решая последние уравнение относительно k, мы заключаем, что в наихудшем случае число проходов равно k=log₂(N+1).

В анализе может помочь и дерево для процесса поиска. В узлах дерева решение стоят элементы, которые проверяются на соответствующем проходе. Элементы, проверка которых будет осуществляться в том случае, если целевое значение меньше текущего элемента, а сравниваемые в случае, если целевое значение больше текущего – в правом поддереве. Дерево решение для списка из 7 элементов изображено на рисунке1. В общем случае дерево относительно сбалансировано, поскольку мы всегда выбираем середину различных частей списка. Поэтому для подсчета числа сравнений мы можем воспользоваться формулами для бинарных деревьев.

Поскольку мы предполагаем, что N=2^k-1, соответствующие дерево решение будет всегда полным. В нем будет k уровней, где k=log₂(N+1). Мы делаем по одному сравнению на каждом уровне, поэтому полное число сравнений не превосходит log₂(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этот алгоритм довольно эффективен, однако для поиска значений из середины списка есть и более эффективные алгоритмы.

Поскольку нам нужно лишь К-ое по величине значение, точное местоположение больших К—&bsol; элементов нас на самом деле не интересует, нам достаточно знать, что они больше искомого. Для всякого элемента из списка весь список распадается на две части: элементы, большие взятого, и меньшие элементы. Если переупорядочить элементы в списке так, чтобы все большие шли за выбранным, а все меньшие — перед ним, и при этом выбранный элемент окажется на Р-ом месте, то мы будем знать, что он Р-ый по величине. Такое переупорядочивание потребует сравнения выбранного элемента со всеми остальными, т.е. 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.