 Найти N меньших элементов множества M, как это можно сделать наиболее быстро? |
Здравствуйте, гость ( Вход | Регистрация )
ViGOur опции профиля:
|
 23.1.2012, 14:06
Сообщение
#1
|
 Мастер  Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация:  40 
 |
Собственно задача в названиии: Найти N меньших элементов множества M, нужен наиболее быстрый алгоритм поиска
M может быть как 100, так и стремиться к бесконечности!  В множестве только числа, от 0 до X. p.s. приводите свои варианты, не стесняйтесь! |
 |
  
|
 |
Ответов
|
cross опции профиля:
|
24.1.2012, 12:40
Сообщение
#2
|
|
Новичок Группа: Новичок Сообщений: 2 Регистрация: 24.6.2010 Пользователь №: 1833 Спасибо сказали: 0 раз(а) Репутация: 0
|
Поправьте если я не прав, но разве поддержание отсортированного списка не сложности logN? Тем самым общая сложность задачи: M*logN? А при не большом Х и достаточной памяти, можно добиться линейности при индексировании элементов.
|
|
|
|
Сообщений в этой теме
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 wiz29 из вышеуказанной постановки, при M->∞ зад... 23.1.2012, 16:57 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 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 |
Теги
Нет тегов для показа
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
Текстовая версия | Сейчас: 4.5.2025, 8:34 |