Дае масив длинной n. Какой есть оптимальный по быстродействию алгоритм поиска 3 максимальных элементов? Банальные модификации BubbleSort не предлагать. И второе, вроде как в STL в какои-то контейнере реалтзован такой алгоритм. Подскажете?

Прямой поиск

std::set. В нем элементы отсортированы.

Модифицируй BFPRT. сложность O(n)
http://en.wikipedia.org/wiki/Selection_algorithm

А проще всего конечно написать прямой поиск. 

Три раза найти максимум - сложность O(n).
Отсортировать и взять три последних - сложность O(n * ln n)

зачем? запоминаем три текущих максимума, берём следующий элемент и сравниваем с минимаксом. Один проход.

не в контейнере, а в алгоритмах: partial_sort

Akina, и сколько придётся сделать сравнений?
MaxPayneC, если три раза - сложность O(3 * n). Во-вторых, как помечать элементы, которые уже максимальны? Ограничений на диапазон нет, так что не получится просто напримео присвоить 1.

Ровно N.

Akina, не знаю. Наверное туплю. Можно пример на каком-нить языке? Или хотя бы словесное описание алгоритма.

Поскольку в std::set элементы отсортированы, то там и будем хранить три максимальных элемента.
1. Берем три первых элемента массива и складываем их в std::set (назовем объект set3).
2. Цикл от 4-го элемента массива и до последнего:
2.1. если он меньше минимального из set3 (*set3.begin()), идем дальше;
2.2. иначе удаляем из set3 минимальный элемент (set3.erase(set3.begin())) и складываем туда текущий из массива.

Добавлено через 1 минуту и 12 секунд
Итого в 2.1 одно сравнение и в 2.2, возможно, еще два сравнения.

Akina, 

По моему вы ошибаетесь сравнений понадобиться в лучшем случае N в худшем 3*N 

Нет.

O(n) = O(3 * n) по определению символов Ландау. Не путайте асимптотическую сложность и константу алгоритма.

По теме: изящнее реализации Pavia я придумать не могу, за исключением того, что начинать имеет смысл от третьего, а не от нулевого элемента, и сравнений в худшем случае будет действительно 3n.

я бы нашел максимальный элемент в массиве, а потом бы перебрал массив и удалил бы это значение... так 3 раза, а сам поиск макс. значения будет быстрый (в большом массиве).... и имеется ввиду что простой перебор массива тоже быстрый? если да, то операция быстрая должна получится...
т.е. в таком случае новый массив(ы), хэш не надо создавать...


(может быть как-то можно еще,  именно 3 последние вывести сразу... а не по одному)

пример сочинил от сюда http://www.opennet.ru/docs/RUS/perl_obzor/...s/quantium.html

Это сообщение отредактировал(а) gcc - 7.3.2010, 11:39

Это не так. Имея 4 значения, можно составить математическое выражение, которое даёт одно из 16 возможных значений в зависимости от того, как распределяются эти значения в результате сортировки (ещё проще - получить номер имнимального), после чего использовать предопределённые команды переприсвоения из массива. При этом явно будет использовано ровно 1 сравнение на каждом этапе (более того, можно обойтись вообще без явных сравнений).
Впрочем, это не влияет на сложность алгоритма - он получается гарантированно линейным O(n).

на какой машитне это будет исполняться? если это обычный современный х86, то есть смысл думать о параллельном алгоритме под 64 разрядную архитектуру, думать о кешировании внутри процессора, если же под виртуальную джава или дотнет машину, то нужно смотреть какие там есть команды,
и для правильного ответа надо знать, насколько отличается задержка и скорость чтения из ОЗУ от скорости чтения процессорных регистров, 

а если задача имеет чисто академический интерес, то гораздо гемморнее будет доказывать оптимаьность алгоритма, чем его придумываение. 

я начинаю думать, что нужен какой-то механизм для выделения ответов, чтобы они были более заметны 

уже десяток посто назад был дан ответ:


ну и на вопрос "как он устроен?" - тоже:




Это сообщение отредактировал(а) maxim1000 - 15.12.2010, 09:46

Мне лично больше по вкусу рецепт Peter'a, просто и со вкусом:

Легко перенести на случай Х максимальных, к тому же за один проход массива О(N). Единственное замечание - для предложенной реализации элементы массива должны быть уникальны.