Собственно задача в названиии: Найти N меньших элементов множества M, нужен наиболее быстрый алгоритм поиска
M может быть как 100, так и стремиться к бесконечности!
В множестве только числа, от 0 до X.
p.s. приводите свои варианты, не стесняйтесь!
qSort
и берёшь N элементов с нужного края.
сделал бы именно так
По условию задачи количество элементов множества может стремиться к бесконечности, в таком случае сколько времени потратит qSort, на сортировку всего множества? И это получается, что для нахождения например 100 элементов, нужно будет отсортировать 2^1000000000000 элементов. Слишком большие затраты...
1) если исходные данные изначально хранить в индексированном виде, то всё элементарно
2) (скрыл спойлером)
самый надежный способ пройти перебором по всем элементам за 1 проход решится данная задача.
ну если доп данных каких то нет о структуре элементов или о законе их изменения и распределения)
Да, забыл сказать, что в множестве только числа, от 0 до X, и лежат они могу как случайны образом, так и упорядочено (смотри худший и лучший случай)
Какие еще нужны доп данные?
из вышеуказанной постановки, при M->∞ задача за конечное время вряд ли решаема))
А что оно тебе даст? Я понимаю, что в случае 0 <= X <= 2 по сравнению с 0 <= X <= 1000 увеличится скорость алгоритма. Но нас то интересует, алгоритм, который будет универсален как для одного, так и для другого случая и так же быстр!
ViGOur, я оговорился - не индексированные, а отсортированные ))
В таком случае будет потрачено кучу времени на сортировку! Лучше тогда уж индексация, времени затратится меньше!
Так что не отходим от условия!
дык, тебе уже написали: пройтись линейно по всему списку и сделать выборку. это самое быстрое решение в один проход.
а ограничение ничего на даёт, если числа рациональные. там между любыми точками может быть бесконечно много значений.
Iron Bug, я знаю ответ. Просто точный ответ, дал только Алексей1153, после чего скрыл спойлером!
От других точного ответа как и от тебя не было!
Так как линейность и называлась, то получается, что алгоритм отработает за O(n + x), но вот х пока не назвали каким будет!
список из N сортированных элементов поддерживать элементарно просто не расходуя на это кучу ресурсов, тк изначально он будет состоять из 1го элемента, затем из 2х и тд, добавлять в сортированный список 1 элемент по моему не проблематично
Это не реальная задача, а чисто алгоритмическая, чтобы мозг расслабить!
алгоритм однопроходный с поддержанием в отсортированном состоянии списка из N наименьших значений.
Поправьте если я не прав, но разве поддержание отсортированного списка не сложности logN? Тем самым общая сложность задачи: M*logN? А при не большом Х и достаточной памяти, можно добиться линейности при индексировании элементов.
ViGOur, так была уже такая тема. Ты же и создавал
http://www.forum.crossplatform.ru/index.php?showtopic=5460
Ну наконец-то! И решение и вспомнили!
Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)