Дае масив длинной 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