Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Поиск 3 максимальных в массиве


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

Автор: Akina 1.3.2010, 14:33
Цитата(HMLd @  1.3.2010,  15:25 Найти цитируемый пост)
Какой есть оптимальный по быстродействию алгоритм поиска 3 максимальных элементов?

Прямой поиск

Автор: Peter 1.3.2010, 18:41
Цитата(HMLd @  1.3.2010,  14:25 Найти цитируемый пост)
вроде как в STL в какои-то контейнере реалтзован такой алгоритм

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

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

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

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

Автор: Akina 1.3.2010, 21:42
Цитата(MaxPayneC @  1.3.2010,  21:52 Найти цитируемый пост)
Три раза найти максимум

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

Автор: Earnest 2.3.2010, 17:08
Цитата(HMLd @  1.3.2010,  15:25 Найти цитируемый пост)
И второе, вроде как в STL в какои-то контейнере реалтзован такой алгоритм. Подскажете? 

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

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

Автор: Akina 3.3.2010, 14:39
Цитата(HMLd @  3.3.2010,  15:34 Найти цитируемый пост)
 и сколько придётся сделать сравнений?

Ровно N.

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

Автор: Peter 3.3.2010, 14:55
Поскольку в 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, возможно, еще два сравнения.

Автор: Pavia 3.3.2010, 20:29
Akina, 
Цитата(Akina @  3.3.2010,  14:39 Найти цитируемый пост)
Ровно N.

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

m1=a[0];
m2=a[2];
m3=a[3];
if (m1>m2)  swap(m1,m2);
if (m2>m3)  swap(m2,m3);
if (m1>m2)  swap(m1,m2);

for(i=0;i<Length(A);i++){
if  (A[i]>m1) {
  m1=A[i];
 if (m1>m2)  {
     swap(m1,m2);
    if (m2>m3)  swap(m2,m3);
   }
 }
}

Автор: esperanto 6.3.2010, 14:30
Цитата(Akina @ 3.3.2010,  14:39)
Цитата(HMLd @  3.3.2010,  15:34 Найти цитируемый пост)
 и сколько придётся сделать сравнений?

Ровно N.

Нет.

Автор: MaxPayneC 7.3.2010, 02:04
Цитата(HMLd @  3.3.2010,  14:34 Найти цитируемый пост)
MaxPayneC, если три раза - сложность O(3 * n).

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

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

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

Код

#!/usr/bin/perl

use Quantum::Superpositions;
my @a = (1,2,3,4,5,6,7,12,9,10);      # integers
print  eigenstates(  any(@a ) >= all(@a)  );

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

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

Автор: Akina 7.3.2010, 11:37
Цитата(Pavia @  3.3.2010,  21:29 Найти цитируемый пост)
По моему вы ошибаетесь сравнений понадобиться в лучшем случае N в худшем 3*N 

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

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

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

Автор: maxim1000 15.12.2010, 09:45
я начинаю думать, что нужен какой-то механизм для выделения ответов, чтобы они были более заметны smile

уже десяток посто назад был дан ответ:
Цитата(Earnest @  2.3.2010,  17:08 Найти цитируемый пост)
partial_sort


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

Цитата(Pavia @  1.3.2010,  20:18 Найти цитируемый пост)
Модифицируй BFPRT. сложность O(n)
http://en.wikipedia.org/wiki/Selection_algorithm

Автор: Silent 25.12.2010, 15:44
Мне лично больше по вкусу рецепт Peter'a, просто и со вкусом:
Код

    for (int i = 0; i < 3; i++) b.insert(a[i]);
    for (int i = 3; i < N; i++) 
    {
        if (a[i] > *b.begin())
        {
            b.erase(b.begin());
            b.insert(a[i]);
        }
    }
    for (std::set<int>::iterator it = b.begin(); it != b.end(); ++it)   printf("%d ",*it);

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)