crossplatform.ru

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

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


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

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

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




Репутация:   40  


Собственно задача в названиии: Найти N меньших элементов множества M, нужен наиболее быстрый алгоритм поиска

M может быть как 100, так и стремиться к бесконечности! :)

В множестве только числа, от 0 до X.

p.s. приводите свои варианты, не стесняйтесь!
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
FantasyOr
  опции профиля:
сообщение 23.1.2012, 15:48
Сообщение #2


Студент
*

Группа: Участник
Сообщений: 75
Регистрация: 13.8.2010
Пользователь №: 1956

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




Репутация:   0  


qSort
и берёшь N элементов с нужного края.
сделал бы именно так
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 23.1.2012, 16:02
Сообщение #3


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

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

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




Репутация:   40  


По условию задачи количество элементов множества может стремиться к бесконечности, в таком случае сколько времени потратит qSort, на сортировку всего множества? И это получается, что для нахождения например 100 элементов, нужно будет отсортировать 2^1000000000000 элементов. Слишком большие затраты...
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 23.1.2012, 16:26
Сообщение #4


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

Группа: Участник
Сообщений: 2939
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

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




Репутация:   34  


1) если исходные данные изначально хранить в индексированном виде, то всё элементарно


2) (скрыл спойлером)

Раскрывающийся текст
ага! Не подглядывай;)если сортировка отпадает, то решение, по-моему, единственное: отсортированный массив результатов с максимальным размером N . Пробегая по исходным данным, нужно проверять, не оказался ли рассматриваемый элемент меньше всех, либо равный наименьшему в массиве результата. Если да - добавить его туда, выбросив самый большой элемент (сохраняя сортировку).

и так , пока не всё

(разумеется, в начале работы массив результатов пуст, потом по элементику растёт до N)


Сообщение отредактировал Алексей1153 - 23.1.2012, 16:31
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 23.1.2012, 16:53
Сообщение #5


Старейший участник
****

Группа: Участник
Сообщений: 600
Регистрация: 7.7.2010
Из: Санкт-Петербург
Пользователь №: 1866

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




Репутация:   12  


самый надежный способ пройти перебором по всем элементам за 1 проход решится данная задача.

ну если доп данных каких то нет о структуре элементов или о законе их изменения и распределения)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 23.1.2012, 16:56
Сообщение #6


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

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

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




Репутация:   40  


Да, забыл сказать, что в множестве только числа, от 0 до X, и лежат они могу как случайны образом, так и упорядочено (смотри худший и лучший случай)

Какие еще нужны доп данные?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 23.1.2012, 16:57
Сообщение #7


Старейший участник
****

Группа: Участник
Сообщений: 600
Регистрация: 7.7.2010
Из: Санкт-Петербург
Пользователь №: 1866

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




Репутация:   12  


из вышеуказанной постановки, при M->∞ задача за конечное время вряд ли решаема:)))

Цитата(ViGOur @ 23.1.2012, 17:56) *
Да, забыл сказать, что в множестве только числа, от 0 до X.

Какие еще нужны доп данные?


Х-конечное?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 23.1.2012, 17:07
Сообщение #8


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

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

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




Репутация:   40  


А что оно тебе даст? Я понимаю, что в случае 0 <= X <= 2 по сравнению с 0 <= X <= 1000 увеличится скорость алгоритма. Но нас то интересует, алгоритм, который будет универсален как для одного, так и для другого случая и так же быстр! :)

Цитата(wiz29 @ 23.1.2012, 17:57) *
из вышеуказанной постановки, при M->∞ задача за конечное время вряд ли решаема:)))
У нас под рукой супер пупер инопланетный сервак, который может посчитать ∞^∞ :D

Цитата(Алексей1153 @ 23.1.2012, 17:26) *
если исходные данные изначально хранить в индексированном виде, то всё элементарно
Ты снова забываешь о том, что у нас может быть огромное количество данных M, которые предназначены для того, чтобы из них получить N наименьших, а ради этого мне думается не стоит индексировать данные.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 23.1.2012, 19:54
Сообщение #9


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

Группа: Участник
Сообщений: 2939
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

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




Репутация:   34  


ViGOur, я оговорился - не индексированные, а отсортированные ))
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 23.1.2012, 22:11
Сообщение #10


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

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

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




Репутация:   40  


В таком случае будет потрачено кучу времени на сортировку! Лучше тогда уж индексация, времени затратится меньше! :)

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

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


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




RSS Текстовая версия Сейчас: 28.3.2024, 19:51