Найти N меньших элементов множества M, как это можно сделать наиболее быстро? Опции

[ViGOur]

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

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

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

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

[FantasyOr]

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

[ViGOur]

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

[Алексей1153]

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


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

Раскрывающийся текст

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

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

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

Сообщение отредактировал Алексей1153 - 23.1.2012, 16:31

[wiz29]

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

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

[ViGOur]

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

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

[wiz29]

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

Да, забыл сказать, что в множестве только числа, от 0 до X.

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

Х-конечное?

[ViGOur]

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

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

У нас под рукой супер пупер инопланетный сервак, который может посчитать ∞^∞

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

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

[Алексей1153]

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

[ViGOur]

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

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