| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Найти K максимальных |
| Автор: killobyte 11.9.2010, 22:01 |
| Требуется найти k максимальных чисел в массиве длиной n. Сложность алгоритма должна быть меньше O(nlogn) |
| Автор: W4FhLF 12.9.2010, 06:26 |
| Например эффективный алгоритм выбора (selection algorithm). Пример описан здесь: http://blogs.msdn.com/b/devdev/archive/2006/01/18/514482.aspx Сложность будет O(n + klogk) < O(nlogn) в большинстве практических случаев. При k == n/2 (что в большинстве случаев в пределах практически значимых задач) функция сложности для обоих случаев выглядит следующим образом:  Хотя в конечно счёте многое будет зависеть от ваших n и реализации самого алгоритма. Достаточно подробно и хорошо эта проблема рассмотрена также у Кормена в книге "Алгоритмы. Построение и анализ". |
| Автор: killobyte 12.9.2010, 11:03 |
| спасибо большое, почитаю книгу. |
| Автор: esperanto 12.9.2010, 16:03 |
| "Сложность будет O(n + klogk) < O(nlogn) в большинстве практических случаев" Формула не верная и лишенная смысла. --------------------- А решение простое, находите к-ую порядковую статистику. И все элементы ее большие и есть вашь ответ Время работы линейное Добавлено через 4 минуты и 9 секунд Статистика находиться за линейное время, без всяких там к лог (к) |
| Автор: W4FhLF 13.9.2010, 08:10 |
| esperanto, K статистика находится за O(n), это верно. А если требуется найти K максимальных не идущих подряд? Ну скажем необходимо взять K чётных максимальных. Тогда будет O(k/2*n) = O(n) чтоли? |
| Автор: baldina 13.9.2010, 08:33 | ||||
знаете линейный алгоритм? хотелось бы увидеть. W4FhLF прав насчет O(n + klogk). Идея - (частичная) сортировка k элементов множества. Partial sort называется. http://www.lsi.upc.edu/~conrado/research/talks/aofa04.pdf |
| Автор: W4FhLF 13.9.2010, 16:11 | ||
Ну вообще линейный алгоритм для k-ой статистики есть. Например вот: http://www.rawkam.com/?p=870 Частичная сортировка необязательнй, перестановки в любом случае необходимы. |
| Автор: baldina 14.9.2010, 08:25 |
| по ссылке алгоритм partial sort, который в худшем случае дает n^2. Линейное время будет в среднем случае (на случайных данных). |
| Автор: W4FhLF 14.9.2010, 09:44 | ||
| baldina, в главе "9.3 Алгоритм выбора с линейным временем работы в наихудшем случае", Кормен, Алгоритмы. Построение и анализ. Цитата, стр. 250:
|
| Автор: baldina 14.9.2010, 10:45 |
| Кормен, насколько я понимаю, ссылается на алгоритм BFPRT. А совсем не то, что по ссылке выше. |
| Автор: W4FhLF 15.9.2010, 06:12 |
| Ты вроде просил привести пример линейного алгоритма? Вот это были примеры. |
| Автор: baldina 15.9.2010, 18:13 |
| спасибо |
| Автор: esperanto 16.9.2010, 00:13 | ||||||||
У случайного алгоритма нет худшего случая. Добавлено через 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) лишен смысла |
| Автор: baldina 16.9.2010, 10:46 | ||||
У случайного алгоритма есть случайный результат 
ок, лучше, чем O(nlogn), меньше, чем O(nlogn). Удовлетворил? и не говорил я, что согласен на большее. а про BFPRT мы знаем, я же упоминал его... вот зацепились за моё "знаете линейный алгоритм". вижу, знаете. вот был бы известен алгоритм, не только приближающийся к теоретической оценке, но и достаточно простой для применения на практике... те слова к этому относились. |
| Автор: esperanto 16.9.2010, 23:07 | ||||||||||
Нет. Лучше яем О(nlog n) не бывает. И меньше не бывает. Для справки О(nlog n) это множество функции, приведу несколько элементов этого множества const, loglog n, log n,sqrt(n),n, n+log n Добавлено через 2 минуты и 2 секунды
У случайного алгоритма результат не случайный а правильный. И быстрая сортировка ,никогда не вернет вам неверный неотсортированный массив. Думаю стоит разобраться в вероятностных алгоритмах. Методах их анализа, и критериев сходимости и концентрации ошибок. |
| Автор: maxdiver 18.9.2010, 12:59 |
offtop, esperanto по-моему решил поразвлекаться и поизмываться над несчастными  даже на экзаменах так к словам не придираются |
| Автор: esperanto 18.9.2010, 13:45 |
| Знаете, вы странный, придирками называете "замечания на неправильные вещи" . Математика точная наука. И еще геддель сказал из неправильной вещи доказуема любая чушь. Мы тут на форуме не знанимаемся доказательством любой чуши. И поэтому, если спрашивать, то надо понимать что спрашиваешь. Я провел экзаменов больше чем вы и никогда ни над кем не измывался, это вам скажет любой мой студент. Посему оставте свои фантазии себе. |
| Автор: maxim1000 18.9.2010, 16:10 |
| Модератор: думаю, пора заканчивать offtopic |
