Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум на CrossPlatform.RU _ Алгоритмы, задачи по программированию, логические игры _ Найти N меньших элементов множества M

Автор: ViGOur 23.1.2012, 14:06

Собственно задача в названиии: Найти N меньших элементов множества M, нужен наиболее быстрый алгоритм поиска

M может быть как 100, так и стремиться к бесконечности! :)

В множестве только числа, от 0 до X.

p.s. приводите свои варианты, не стесняйтесь!

Автор: FantasyOr 23.1.2012, 15:48

qSort
и берёшь N элементов с нужного края.
сделал бы именно так

Автор: ViGOur 23.1.2012, 16:02

По условию задачи количество элементов множества может стремиться к бесконечности, в таком случае сколько времени потратит qSort, на сортировку всего множества? И это получается, что для нахождения например 100 элементов, нужно будет отсортировать 2^1000000000000 элементов. Слишком большие затраты...

Автор: Алексей1153 23.1.2012, 16:26

1) если исходные данные изначально хранить в индексированном виде, то всё элементарно


2) (скрыл спойлером)

Раскрывающийся текст
ага! Не подглядывай;)если сортировка отпадает, то решение, по-моему, единственное: отсортированный массив результатов с максимальным размером N . Пробегая по исходным данным, нужно проверять, не оказался ли рассматриваемый элемент меньше всех, либо равный наименьшему в массиве результата. Если да - добавить его туда, выбросив самый большой элемент (сохраняя сортировку).

и так , пока не всё

(разумеется, в начале работы массив результатов пуст, потом по элементику растёт до N)

Автор: wiz29 23.1.2012, 16:53

самый надежный способ пройти перебором по всем элементам за 1 проход решится данная задача.

ну если доп данных каких то нет о структуре элементов или о законе их изменения и распределения)

Автор: ViGOur 23.1.2012, 16:56

Да, забыл сказать, что в множестве только числа, от 0 до X, и лежат они могу как случайны образом, так и упорядочено (смотри худший и лучший случай)

Какие еще нужны доп данные?

Автор: wiz29 23.1.2012, 16:57

из вышеуказанной постановки, при M->∞ задача за конечное время вряд ли решаема:)))

Цитата(ViGOur @ 23.1.2012, 17:56) *
Да, забыл сказать, что в множестве только числа, от 0 до X.

Какие еще нужны доп данные?


Х-конечное?

Автор: ViGOur 23.1.2012, 17:07

А что оно тебе даст? Я понимаю, что в случае 0 <= X <= 2 по сравнению с 0 <= X <= 1000 увеличится скорость алгоритма. Но нас то интересует, алгоритм, который будет универсален как для одного, так и для другого случая и так же быстр! :)

Цитата(wiz29 @ 23.1.2012, 17:57) *
из вышеуказанной постановки, при M->∞ задача за конечное время вряд ли решаема:)))
У нас под рукой супер пупер инопланетный сервак, который может посчитать ∞^∞ :D

Цитата(Алексей1153 @ 23.1.2012, 17:26) *
если исходные данные изначально хранить в индексированном виде, то всё элементарно
Ты снова забываешь о том, что у нас может быть огромное количество данных M, которые предназначены для того, чтобы из них получить N наименьших, а ради этого мне думается не стоит индексировать данные.

Автор: Алексей1153 23.1.2012, 19:54

ViGOur, я оговорился - не индексированные, а отсортированные ))

Автор: ViGOur 23.1.2012, 22:11

В таком случае будет потрачено кучу времени на сортировку! Лучше тогда уж индексация, времени затратится меньше! :)

Так что не отходим от условия! :)

Автор: Iron Bug 23.1.2012, 23:24

дык, тебе уже написали: пройтись линейно по всему списку и сделать выборку. это самое быстрое решение в один проход.

а ограничение ничего на даёт, если числа рациональные. там между любыми точками может быть бесконечно много значений.

Автор: ViGOur 24.1.2012, 7:24

Iron Bug, я знаю ответ. Просто точный ответ, дал только Алексей1153, после чего скрыл спойлером! :D
От других точного ответа как и от тебя не было! :)

Так как линейность и называлась, то получается, что алгоритм отработает за O(n + x), но вот х пока не назвали каким будет!

Автор: wiz29 24.1.2012, 9:04

список из N сортированных элементов поддерживать элементарно просто не расходуя на это кучу ресурсов, тк изначально он будет состоять из 1го элемента, затем из 2х и тд, добавлять в сортированный список 1 элемент по моему не проблематично

Цитата(ViGOur @ 23.1.2012, 18:07) *
А что оно тебе даст? Я понимаю, что в случае 0 <= X <= 2 по сравнению с 0 <= X <= 1000 увеличится скорость алгоритма. Но нас то интересует, алгоритм, который будет универсален как для одного, так и для другого случая и так же быстр! :)


Видимо просто не понятен был смысл вопроса, когда о природе чисел известно больше, то возможна какая то оптимизация, изменение одного инфинитивного интервала на другой ровным счетом не добавляет никаких новых знаний о природе чисел из множества X.

Автор: ViGOur 24.1.2012, 9:08

Это не реальная задача, а чисто алгоритмическая, чтобы мозг расслабить! ;)

Автор: wiz29 24.1.2012, 10:29

алгоритм однопроходный с поддержанием в отсортированном состоянии списка из N наименьших значений.

Автор: cross 24.1.2012, 12:40

Поправьте если я не прав, но разве поддержание отсортированного списка не сложности logN? Тем самым общая сложность задачи: M*logN? А при не большом Х и достаточной памяти, можно добиться линейности при индексировании элементов.

Автор: igor_bogomolov 24.1.2012, 13:10

ViGOur, так была уже такая тема. Ты же и создавал
http://www.forum.crossplatform.ru/index.php?showtopic=5460

Автор: ViGOur 24.1.2012, 13:32

Ну наконец-то! И решение и вспомнили! :D

Автор: AD 24.1.2012, 14:10

Цитата(ViGOur @ 24.1.2012, 14:32) *
Ну наконец-то! И решение и вспомнили! :D

Перечитал ту тему.

А твое решение без использования STL так и не увидели.

Хотя решение в последних двух постах очень понравилось!

Все украдено до нас! :)

Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)