crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

2 страниц V  < 1 2  
Ответить в данную темуНачать новую тему
> Найти N меньших элементов множества M, как это можно сделать наиболее быстро?
Iron Bug
  опции профиля:
сообщение 23.1.2012, 23:24
Сообщение #11


Профессионал
*****

Группа: Модератор
Сообщений: 1587
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 218 раз(а)




Репутация:   12  


дык, тебе уже написали: пройтись линейно по всему списку и сделать выборку. это самое быстрое решение в один проход.

а ограничение ничего на даёт, если числа рациональные. там между любыми точками может быть бесконечно много значений.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 24.1.2012, 7:24
Сообщение #12


Мастер
******

Группа: Модератор
Сообщений: 3290
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


Iron Bug, я знаю ответ. Просто точный ответ, дал только Алексей1153, после чего скрыл спойлером! :D
От других точного ответа как и от тебя не было! :)

Так как линейность и называлась, то получается, что алгоритм отработает за 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


Мастер
******

Группа: Модератор
Сообщений: 3290
Регистрация: 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


Мастер
******

Группа: Модератор
Сообщений: 3290
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


Ну наконец-то! И решение и вспомнили! :D
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
AD
  опции профиля:
сообщение 24.1.2012, 14:10
Сообщение #19


Профессионал
*****

Группа: Участник
Сообщений: 2003
Регистрация: 4.2.2008
Из: S-Petersburg
Пользователь №: 84

Спасибо сказали: 70 раз(а)




Репутация:   17  


Цитата(ViGOur @ 24.1.2012, 14:32) *
Ну наконец-то! И решение и вспомнили! :D

Перечитал ту тему.

А твое решение без использования STL так и не увидели.

Хотя решение в последних двух постах очень понравилось!

Все украдено до нас! :)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

2 страниц V  < 1 2
Ответить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 20.10.2019, 12:15