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.