10 максимальных элементов

Кто подскажет.
Есть массив больше 2000 положительных чисел.

Как определить первые десять максимальных чисел.

сколько дней назад с программированием познакомился?? ;D
заводишь массив из 10 чисел, записываешь туда нули. просматриваешь большой массив по порядку, если какое либо число в малом массиве меньше текущего числа, записываешь на его место таковое число.

vot и всё ;D

Сообщение отредактировано: wormball - 05.09.03, 14:05

Цитата

заводишь массив из 10 чисел, записываешь туда нули

Не пойдет... по одно простой причине
Есть вероятность, что все числа отрицательные
Закидывать надо не нули, а 1е число из проверяемых!

Цитата Black_Star, 05.09.03, 20:55:35

Есть вероятность, что все числа отрицательные

Цитата Rembo99, 05.09.03, 14:06:45

Есть массив больше 2000 положительных чисел.

;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D

Sorry невнимательно прочитал...

Цитата Black_Star, 06.09.03, 02:56:47

Sorry невнимательно прочитал...

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

Цитата wormball, 08.09.03, 15:25:44

число надо записывать не просто на место любого числа, его меньшего, а на место наименьшего из 10ти чисел.

Медленно, но верно движемся в сторону сортировки

да, но сортировать большой массив не имеет смысла, ведь тогда будет сложность n ln n, а так сложность просто n. можно, конечно, рассортировать маленький массив, а потом старательно поддерживать его в отсортированном состоянии, но я думаю, что так будет ничуть не быстрее.

И так правильный ответ   О(п).


1) порядковые статистики алгоритм который позволяет найти любой порядковый эл-т
(мин-й или втор-й мин-й или средний и т.п) за О(п)


2) Применить в цикле 10 раз


ВСе

повремени также (в смысле считаться будет за такое же время)

Цитата

твоя невнимательность куда более велика, чем ты думаешь

Плохой ты

А заполнить маленький массив просто...
S(2000)
M(10)
X:=1:X2:=1
m(x):=max(s(i))
x:=x+x2
if x>9 or x<2 then x2:=-x2
и т.д...
В вопросе нет указаний, чтобы они шли в порядке возрастания...

Вот еще решение

1) строим кучу   0(п)
2) удаляем 10 раз макс-элемент 0(лог(п))

-------------
0(п)

и замечу не нужна дополнительная память

Начинаем сортировку вставками и завершаем после 1 прохода

Сообщение отредактировано: Trurl - 10.09.03, 12:55

Цитата Trurl, 10.09.03, 16:44:04

Начинаем сортировку вставками и завершаем после 1 прохода

какой проход в сортировке ставками и почему после первого и какова сложность и кажись не правильно

Цитата esperanto, 10.09.03, 14:28:54

1) строим кучу   0(п)

я конечно всё про кучи уже забыл, но помоему куча строится посложнее.

Цитата esperanto, 10.09.03, 17:08:04

какой проход в сортировке ставками и почему после первого и какова сложность и кажись не правильно

Во, блин, написал. Самому непонятно. Попробую еще раз.
Для каждого элемента большого массива делаем вставку в маленький.
Сложность O(m*n)

Кстати, построение пирамиды O(n*log(n))

У меня есть файл со строками формата:
поле1|поле2|поле3|поле4|поле5|
Пример:
12|34|54|89|54|
13|67|70|3|88|
и т.д....

И мне из этого файла надо было отобрать 10 строк с
самыми максимальными элементами в поле5.
Вот мое решение на Perl
функция получает ссылку на массив в который заранее был прочитан файл
и возвращает ссылку уже на искомый массив.
Пожалуста подскажите можно ли эту функцию оптимизировать (решения только на Perl)
Главное вникните в суть задачи

sub Get10Max {

     my ($r_data) = @_;#ссылка на массив
     my (@tmp_max) = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);#заполнили временный массив
     my (@max);#а вот сюда в конце и попадут 10 макс
     my ($i, $tmp_var);
     my $best = $tmp_max[0];#
     
     for $i(0..$#$r_data) {
           $tmp_var = (split(/\|/, $r_data->[$i]))[4];#выдернули последнее число из строки массива
           my ($m, $min, $index, $flag);
           $flag = 0;
           if ($tmp_var > $best) {#маленький массив сортируем
                       # только когда текущий элемент из большого больше мин из маленького
              $min = $tmp_max[0];
              for $m(0..$#lider) {
                    if ($min > $tmp_max[$m]) {
                         $min = $tmp_max[$m];
                         $index = $m;
                    }
              }
           $flag = 1;#нашли мин
           $best = $min;#для следующего цикла
           }
           if ($flag) {
              $tmp_max[$index] = $tmp_var;#этот массив мы сортируем
              $max[$index] = $i;#мне нужны строки а не
                       #отдельные эл поэтому запоминаем индексы большого массива
           }
     }
     $i = 0;
     for $i(0..$#max) {
           $max[$i] = $r_data->[$max[$i]];#вставляем полные строки из большого массива
     }
     undef $r_data;
     undef @tmp_max;

     return \@max;
}

Цитата wormball, 10.09.03, 17:25:43

я конечно всё про кучи уже забыл, но помоему куча строится посложнее.

Я по кучам специалист! зы

и все таки за линейное время

Цитата esperanto, 10.09.03, 21:45:40

Я по кучам специалист! зы

и все таки за линейное время

Алгоритм+анализ, плз!

1)  троим кучу по известному алг-му binary heap 0(n) (есть в инете)
2) удаляем из кучи 10 раз минимальный эл-т 10*log(n)

-------
O(n+lg(n)) ==> 0(n)

Понял, я с деревьями попутал  :(.
Но при простом выборе максимального имеем те же 10*O(n) = O(n)