 Найти 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 опции профиля:
|
24.1.2012, 9:04
Сообщение
#2
|
 Старейший участник Группа: Участник Сообщений: 600 Регистрация: 7.7.2010 Из: Санкт-Петербург Пользователь №: 1866 Спасибо сказали: 94 раз(а) Репутация: 12
|
список из N сортированных элементов поддерживать элементарно просто не расходуя на это кучу ресурсов, тк изначально он будет состоять из 1го элемента, затем из 2х и тд, добавлять в сортированный список 1 элемент по моему не проблематично
Цитата(ViGOur @ 23.1.2012, 18:07)  А что оно тебе даст? Я понимаю, что в случае 0 <= X <= 2 по сравнению с 0 <= X <= 1000 увеличится скорость алгоритма. Но нас то интересует, алгоритм, который будет универсален как для одного, так и для другого случая и так же быстр! Видимо просто не понятен был смысл вопроса, когда о природе чисел известно больше, то возможна какая то оптимизация, изменение одного инфинитивного интервала на другой ровным счетом не добавляет никаких новых знаний о природе чисел из множества 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 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 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 |
Теги
Нет тегов для показа
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
Текстовая версия | Сейчас: 1.12.2024, 2:41 |