 Найти N меньших элементов множества M, как это можно сделать наиболее быстро? |
Здравствуйте, гость ( Вход | Регистрация )
ViGOur опции профиля:
|
 23.1.2012, 14:06
Сообщение
#1
|
 Мастер  Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация:  40 
 |
Собственно задача в названиии: Найти N меньших элементов множества M, нужен наиболее быстрый алгоритм поиска
M может быть как 100, так и стремиться к бесконечности!  В множестве только числа, от 0 до X. p.s. приводите свои варианты, не стесняйтесь! |
 |
  
|
 |
Ответов
|
wiz29 опции профиля:
|
23.1.2012, 16:57
Сообщение
#2
|
 Старейший участник Группа: Участник Сообщений: 600 Регистрация: 7.7.2010 Из: Санкт-Петербург Пользователь №: 1866 Спасибо сказали: 94 раз(а) Репутация: 12
|
из вышеуказанной постановки, при M->∞ задача за конечное время вряд ли решаема
))Цитата(ViGOur @ 23.1.2012, 17:56)  Да, забыл сказать, что в множестве только числа, от 0 до X. Какие еще нужны доп данные? Х-конечное? |
|
|
|
Сообщений в этой теме
ViGOur Найти N меньших элементов множества M 23.1.2012, 14:06
FantasyOr qSort
и берёшь N элементов с нужного края.
сделал ... 23.1.2012, 15:48 ViGOur По условию задачи количество элементов множества м... 23.1.2012, 16:02 Алексей1153 1) если исходные данные изначально хранить в индек... 23.1.2012, 16:26 wiz29 самый надежный способ пройти перебором по всем эле... 23.1.2012, 16:53 ViGOur Да, забыл сказать, что в множестве только числа, о... 23.1.2012, 16:56 ViGOur А что оно тебе даст? Я понимаю, что в случае 0 ... 23.1.2012, 17:07 Алексей1153 ViGOur, я оговорился - не индексированные, а отсор... 23.1.2012, 19:54 ViGOur В таком случае будет потрачено кучу времени на сор... 23.1.2012, 22:11 Iron Bug дык, тебе уже написали: пройтись линейно по всему ... 23.1.2012, 23:24 ViGOur Iron Bug, я знаю ответ. Просто точный ответ, дал т... 24.1.2012, 7:24 wiz29 список из N сортированных элементов поддерживать э... 24.1.2012, 9:04 ViGOur Это не реальная задача, а чисто алгоритмическая, ч... 24.1.2012, 9:08 wiz29 алгоритм однопроходный с поддержанием в отсортиров... 24.1.2012, 10:29 cross Поправьте если я не прав, но разве поддержание отс... 24.1.2012, 12:40 igor_bogomolov ViGOur, так была уже такая тема. Ты же и создавал
... 24.1.2012, 13:10
ViGOur Ну наконец-то! И решение и вспомнили! 24.1.2012, 13:32 AD Цитата(ViGOur @ 24.1.2012, 14:32) Ну нако... 24.1.2012, 14:10 |
Теги
Нет тегов для показа
9 чел. читают эту тему (гостей: 9, скрытых пользователей: 0)
Пользователей: 0
|
|
Текстовая версия | Сейчас: 28.11.2024, 8:52 |