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

      Поскольку мы предполагаем, что 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 этот алгоритм довольно эффективен, однако для поиска значений из середины списка есть и более эффективные алгоритмы.

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