 Найти N меньших элементов множества M, как это можно сделать наиболее быстро? |
Здравствуйте, гость ( Вход | Регистрация )
  |
Iron Bug опции профиля:
|
 23.1.2012, 23:24
Сообщение
#11
|
 Профессионал  Группа: Модератор Сообщений: 1611 Регистрация: 6.2.2009 Из: Yekaterinburg Пользователь №: 533 Спасибо сказали: 219 раз(а) Репутация:  12 
 |
дык, тебе уже написали: пройтись линейно по всему списку и сделать выборку. это самое быстрое решение в один проход.
а ограничение ничего на даёт, если числа рациональные. там между любыми точками может быть бесконечно много значений. |
 |
  
|
|
ViGOur опции профиля:
|
24.1.2012, 7:24
Сообщение
#12
|
 Мастер Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: 40
|
Iron Bug, я знаю ответ. Просто точный ответ, дал только Алексей1153, после чего скрыл спойлером!
 От других точного ответа как и от тебя не было!  Так как линейность и называлась, то получается, что алгоритм отработает за O(n + x), но вот х пока не назвали каким будет! |
|
|
|
|
wiz29 опции профиля:
|
24.1.2012, 9:04
Сообщение
#13
|
 Старейший участник Группа: Участник Сообщений: 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 опции профиля:
|
24.1.2012, 9:08
Сообщение
#14
|
|
Мастер Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: 40
|
Это не реальная задача, а чисто алгоритмическая, чтобы мозг расслабить!
|
|
|
|
|
wiz29 опции профиля:
|
24.1.2012, 10:29
Сообщение
#15
|
|
Старейший участник Группа: Участник Сообщений: 600 Регистрация: 7.7.2010 Из: Санкт-Петербург Пользователь №: 1866 Спасибо сказали: 94 раз(а) Репутация: 12
|
алгоритм однопроходный с поддержанием в отсортированном состоянии списка из N наименьших значений.
|
|
|
|
|
cross опции профиля:
|
24.1.2012, 12:40
Сообщение
#16
|
|
Новичок Группа: Новичок Сообщений: 2 Регистрация: 24.6.2010 Пользователь №: 1833 Спасибо сказали: 0 раз(а) Репутация: 0
|
Поправьте если я не прав, но разве поддержание отсортированного списка не сложности logN? Тем самым общая сложность задачи: M*logN? А при не большом Х и достаточной памяти, можно добиться линейности при индексировании элементов.
|
|
|
|
|
igor_bogomolov опции профиля:
|
24.1.2012, 13:10
Сообщение
#17
|
|
Профессионал Группа: Сомодератор Сообщений: 1215 Регистрация: 22.3.2009 Из: Саратов Пользователь №: 630 Спасибо сказали: 235 раз(а) Репутация: 29
|
ViGOur, так была уже такая тема. Ты же и создавал
http://www.forum.crossplatform.ru/index.php?showtopic=5460 |
|
|
|
|
ViGOur опции профиля:
|
24.1.2012, 13:32
Сообщение
#18
|
|
Мастер Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: 40
|
Ну наконец-то! И решение и вспомнили!
|
|
|
|
|
AD опции профиля:
|
24.1.2012, 14:10
Сообщение
#19
|
|
Профессионал Группа: Участник Сообщений: 2003 Регистрация: 4.2.2008 Из: S-Petersburg Пользователь №: 84 Спасибо сказали: 70 раз(а) Репутация: 17
|
Цитата(ViGOur @ 24.1.2012, 14:32) Ну наконец-то! И решение и вспомнили! Перечитал ту тему. А твое решение без использования STL так и не увидели. Хотя решение в последних двух постах очень понравилось! Все украдено до нас!
|
|
|
|
|
Теги
Нет тегов для показа
4 чел. читают эту тему (гостей: 4, скрытых пользователей: 0)
Пользователей: 0
|
|
Текстовая версия | Сейчас: 1.12.2024, 6:29 |