выборка из несортированного списка

From

Alexey Kruglov (2:5015/70.5)

To

Stepan M Pechkin

Date

2002-08-12T22:33:11Z

Area

RU.ALGORITHMS

nPuBeT, Stepan!

Вторник 30 Июля 2002 21:36, Stepan M Pechkin wrote to All:

 SP>     Дан несортированный список длиной n. Из него нужно выбрать _по
 SP> порядку_ lg(n) максимальных элементов за количество операций, линейное
 SP> от n. Второй вопрос: насколько можно увеличить количество выбираемых
 SP> по порядку максимальных, чтобы все еще укладываться в линейное время?
Никто, вроде, не ответил, так что отвечу.

1. Можно построить кучу из этих элементов за время O(n), потом выбрать k
максимальных в подрядке убывания за O(k ln n), т.к. из кучи можно достать max
элемент за O(ln n). => при k=ln(n) это все будет работать за O(n+k ln n)=O(n).

2. При k=O(n/ln n) тоже будет работать за O(n).

Про кучи (heap; не та, в которой выделяется динамическая память, а та, которая
в heapsort) есть, например, в
 Кормен, Лейзерсон, Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.
В последнем переводе Кнута кучи называются пирамидами.

nOkA. Alexey.

--- GoldED+/386 1.1.4.7
 * Origin:  6DFA 1186 7576 DE60 6CCB  EB39 AD81 1733 EEBB 970A  (2:5015/70.5)