2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Нужен оптимальный алгоритм решения
Сообщение02.06.2010, 19:29 
Аватара пользователя
Здравствуйте.
задача такова.

есть множество обьектов скажем например штук 1000
есть некая функция которая присваивает 10-ти обьектам ранг от 1 до 10.

Нужно раставить обьекты в множестве по мере спада ранга.

решение есть:
1.берем первые 10, определяем какой из них с самым меньшим рангом
2. на его место ставим 11 элемент и опять определяем обьект с самым меньшим рангом..
3. повторяем пункт 2 пока не дойдем до конца
так мы определим обьект с самым большим рангом.. откидываем его, а с оставшимися обьектами проводим все по пунктам 1,2,3..
Те элементы что откидывали образуют отсортированное множество.
При таком алгоритме количество обращений к функции определения ранга ~1милион

Подскажите пожалуйста алгоритм при котором число обращений к функции определения ранга было минимальным.

 
 
 
 Re: Нужен оптимальный алгоритм решения
Сообщение02.06.2010, 20:51 
Например, так:
1. Выбираем 1 случайный элемент. Сравниваем с ним по 9 остальных элементов и делим их на те, что меньше референсного, и те, что больше.
2. Рекурсивно сортируем получившиеся 2 под-массива.

Для улучшения можно взять несколько (2...9) референсных элементов, предварительно их отсортировав.
Самостоятельно проанализируйте, какое количество референсных элементов оптимально.

-- Ср июн 02, 2010 13:58:24 --

barss в сообщении #326877 писал(а):
решение есть:
1.берем первые 10, определяем какой из них с самым меньшим рангом
2. на его место ставим 11 элемент и опять определяем обьект с самым меньшим рангом.
Кстати, даже Ваш вариант легко ускорить в 9 раз, если на каждой итерации сравнивать текущий минимальный с 9-ю новыми.
А можно ускорить и в 25 раз, если за один проход искать сразу 5 минимальных элементов.
Но это всё равно будет квадратичный алгоритм, а то, что предложил я - $O(N\log N)$, причём с константой сильно меньше единицы, т.е. быстрее, чем quicksort.

 
 
 
 Re: Нужен оптимальный алгоритм решения
Сообщение02.06.2010, 21:58 
Аватара пользователя
огромное спасибо Вам!

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group