crossplatform.ru

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

7 страниц V  « < 5 6 7  
Ответить в данную темуНачать новую тему
> Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более
Алексей1153
  опции профиля:
сообщение 25.1.2012, 20:14
Сообщение #61


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

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

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




Репутация:   34  


Цитата(panter_dsd @ 25.1.2012, 14:41) *
1. rValue = ++n; - зачем в 2 строки делать?


моё мнение - именно в 2 строки лучше. Нагляднее, плюс исключена ошибка. А то, что постфикс у простого типа - так это оптимизатор исправит сам, зато так красивее для глаза )
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 26.1.2012, 16:07
Сообщение #62


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

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

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




Репутация:   12  


Цитата(ViGOur @ 25.1.2012, 11:59) *
Как и обещал, код:


Сложность приведенного алгоритма О(M*N), можно сделать быстрее за O(log2(M)*N), но он сложней в реализации.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 26.1.2012, 20:08
Сообщение #63


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

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

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




Репутация:   40  


Объясни как. Можно использовать только два массива! :)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 27.1.2012, 8:58
Сообщение #64


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

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

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




Репутация:   12  


Цитата(ViGOur @ 26.1.2012, 21:08) *
Объясни как. Можно использовать только два массива! :)


Множитель 'M' берется из линейности поиска в массиве значений, если данный массив поддерживать в сортированном виде, то поиск будет обходится в O(log2(M)), соответственно, получим более выгодную оценку для поиска.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
cross
  опции профиля:
сообщение 27.1.2012, 11:46
Сообщение #65


Новичок


Группа: Новичок
Сообщений: 2
Регистрация: 24.6.2010
Пользователь №: 1833

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




Репутация:   0  


Цитата(wiz29 @ 26.1.2012, 17:07) *
Сложность приведенного алгоритма О(M*N), можно сделать быстрее за O(log2(M)*N), но он сложней в реализации.


Согласен (о чем и писал ранее в соседней теме про эту задачу). Единственный линейный алгоритм, который мне видится, это если значение элементов лежит в интервале от 0 до Х (где Х не велико и нам хватает памяти) заводим массив из Х элементов, в котором индекс - это величина элемента в исходном множестве, а значение - число появлений этого элемента в исходном множестве. За один проход пересчитываем все элементы и берем нужное количество минимальных.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

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


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




RSS Текстовая версия Сейчас: 15.12.2019, 6:03