Требуется найти k максимальных чисел в массиве длиной n.
Сложность алгоритма должна быть меньше O(nlogn)

Это сообщение отредактировал(а) killobyte - 11.9.2010, 22:22

Например эффективный алгоритм выбора (selection algorithm). Пример описан здесь: http://blogs.msdn.com/b/devdev/archive/200.../18/514482.aspx

Сложность будет  O(n + klogk) < O(nlogn) в большинстве практических случаев. При k == n/2 (что в большинстве случаев в пределах практически значимых задач) функция сложности для обоих случаев выглядит следующим образом:



Хотя в конечно счёте многое будет зависеть от ваших n и реализации самого алгоритма. 

Достаточно подробно и хорошо эта проблема рассмотрена также у Кормена в книге "Алгоритмы. Построение и анализ". 

спасибо большое, почитаю книгу.

"Сложность будет  O(n + klogk) < O(nlogn) в большинстве практических случаев"

Формула не верная и лишенная смысла.







---------------------
А решение простое, находите к-ую порядковую статистику.  И все элементы ее большие и есть вашь ответ
Время работы линейное

Добавлено через 4 минуты и 9 секунд
Статистика находиться за линейное время, без всяких там  к лог (к)

esperanto, K статистика находится за O(n), это верно. А если требуется найти K максимальных не идущих подряд? Ну скажем необходимо взять K чётных максимальных. Тогда будет O(k/2*n) = O(n) чтоли?

знаете линейный алгоритм? хотелось бы увидеть.

W4FhLF прав насчет O(n + klogk). Идея - (частичная) сортировка k элементов множества. Partial sort называется.
http://www.lsi.upc.edu/~conrado/research/talks/aofa04.pdf

Ну вообще линейный алгоритм для k-ой статистики есть. Например вот: http://www.rawkam.com/?p=870
Частичная сортировка необязательнй, перестановки в любом случае необходимы. 

Это сообщение отредактировал(а) W4FhLF - 13.9.2010, 16:13

по ссылке алгоритм partial sort, который в худшем случае дает n^2. Линейное время будет в среднем случае (на случайных данных).

baldina, в главе "9.3 Алгоритм выбора с линейным временем работы в наихудшем случае", Кормен, Алгоритмы. Построение и анализ. 

Цитата, стр. 250:

Кормен, насколько я понимаю, ссылается на алгоритм BFPRT. А совсем не то, что по ссылке выше.

Ты вроде просил привести пример линейного алгоритма? Вот это были примеры.

спасибо

У случайного алгоритма нет худшего случая.

Добавлено через 1 минуту и 32 секунды
A worst-case linear algorithm for the general case of selecting the kth largest element was published by Blum, Floyd, Pratt, Rivest and Tarjan in their 1973 paper "Time bounds for selection", sometimes called BFPRT after the last names of the authors. It is based on the quickselect algorithm and is also known as the median-of-medians algorithm.

Although quickselect is linear-time on average, it can require quadratic time with poor pivot choices (consider the case of pivoting around the smallest element at each step). The solution to make it O(n) in the worst case is to consistently find "good" pivots. A good pivot is one for which we can establish that a constant proportion of elements fall both below and above it.

The Select algorithm divides the list into groups of five elements. (Left over elements are ignored for now.) Then, for each group of five, the median is calculated (an operation that can potentially be made very fast if the five values can be loaded into registers and compared). (If sorting in-place, then these medians are moved into one contiguous block in the list.) Select is then called recursively on this sublist of n/5 elements to find their true median. Finally, the "median of medians" is chosen to be the pivot.

Добавлено через 3 минуты и 5 секунд

Вы сами себе противоречите то просите алгоритм
Быстрее чем O(nlogn)  

То говорите согласен и на большее.

Кроме всего прочего ПОВТОРЮ

термин быстрее чем O(nlogn)  лишен смысла

У случайного алгоритма есть случайный результат 


ок, лучше, чем O(nlogn), меньше, чем O(nlogn). Удовлетворил?

и не говорил я, что согласен на большее.

а про BFPRT мы знаем, я же упоминал его...
вот зацепились за моё "знаете линейный алгоритм". вижу, знаете.
вот был бы известен алгоритм, не только приближающийся к теоретической оценке, но и достаточно простой для применения на практике... те слова к этому относились.

Нет. 

Лучше яем О(nlog n) не бывает. И  меньше не бывает.

Для справки  О(nlog n) это множество функции, приведу несколько элементов этого множества const, loglog n, log n,sqrt(n),n, n+log n

Добавлено через 2 минуты и 2 секунды

У случайного алгоритма результат не случайный а правильный. И быстрая сортировка ,никогда не вернет вам неверный неотсортированный массив. 

Думаю стоит разобраться в вероятностных алгоритмах. Методах их анализа, и критериев сходимости и концентрации ошибок.