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

From

Alexey Kruglov (2:5015/70.5)

To

Stepan M Pechkin

Date

2002-08-17T19:19Z

Area

RU.ALGORITHMS

nPuBeT, Stepan!

Пятница 16 Августа 2002 13:11, Stepan M Pechkin wrote to Alexey Kruglov:

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

 AK>> 1. Можно построить кучу из этих элементов за время O(n), потом
 AK>> выбрать k
 SP>     Это, простите, как?
См. "Алгоритмы: построение и анализ", п. 7.3. Тот же алгоритм построения кучи у
Шеня, зад. 4.2.1, "сделать 1-поддерево регулярным", но там не доказывается, что
это делается за O(n). Второй вариант сортировки во втором решении -- сортировка
кучей.

 AK>> максимальных в подрядке убывания за O(k ln n), т.к. из кучи можно
 AK>> достать max элемент за O(ln n).
 SP>     А разве не за O(1)?
Найти можно за O(1). Я имел в виду, что он еще и удаляется после этого.

 SP>     Что мы называем кучей? Реализацию бинарного дерева поиска через
 SP> массив?
Нет. Куча -- двоичное дерево, вершины которого имеют номера 1, ... , n. Вершина
1 -- корень, родитель вершины i -- [i/2]. В каждой вершине сожержится запись,
запись родителя больше записей его сыновей (в отличие от деревьев поиска).
Можно построить кучу по данным записям за O(n), добавить или удалить запись за
O(ln n), найти max запись за O(1).

 AK>>  => при k=ln(n) это все будет работать за O(n+k ln n)=O(n).
 SP>     А каким образом O(n lg n) = O(n)?
Мне тоже интересно. А откуда ты это взял? n+k ln n = n+(k*ln(n)).

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

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

 SP>     Решение было другое. Даже два. Одно - разбить массив на пятерки, в
[...]
 SP> у Шеня в 7-ой главе, задача 7.4.8 ("имеется изящный, хотя
 SP> и практически бесполезный, способ..." :-)
Тут тоже можно найти и отсортировать O(n/ln n) max элементов за O(n).

 SP>     И второе: разбиваем массив на пары, в каждой паре находим
 SP> максимум, потом максимумы попарно сравниваем, и так пока не найдется
 SP> максимальный. Его берем. Затем ищем второй по величине. Он где-нибудь
 SP> непременно встречался с
 SP> максимальным в получившемся дереве. Идем от максимального к корню - и
 SP> находим его. Так же и все остальные (lg n)-2. Нетрудно подсчитать, что
 SP> в O(n) укладывается.
Это почти то же самое, что и у меня, только вместо кучи используется дерево
выбора. Эксперимены показали, что с деревом выбора надо примерно в 2 раза
меньше сравнений. Даже при k=n, т.е. сортировка выбором из дерева требует
меньше сравнений, чем кучей.

Эта задача, как оказалось, есть в "Алгоритмах...", зад. 10-1.

Теперь про твой второй вопрос в исходном письме. Докажем, что k не может быть
больше O(n/ln n).

Можно получить нижнюю оценку на число сравнений (если мы можем только
сравнивать элементы), как и для обычной сортировки. Пусть T(n,k) -- наибольшее
кол-во сравнений при сортировке k максимальных из n элементов каким-нибудь
алгритмом. Тогда при достаточно больших n и (n-k) и некотором C

  T(n,k)*ln 2 >= (n-k+1/2)ln 1/(1-k/n) + k(ln n-1) - C/(n-k).

(У умножения и деления приоритет меньше, чем у ln, но больше, чем у сложения и
вычитания.)

Отсюда можно получить, что при любой зависимости k(n), такой что k(n)/n -> 0,

  T(n,k(n)) >= k(ln n+o(1))/ln 2 = \Omega(k ln n),

где o(1) -> 0 при n -> +\infty.

Если какой-то алгоритм при какой-то зависимости k(n) работает линейное время,
то cn \geq T(n,k(n)) >= c_2 k ln n, т.к. можно доказать, что из линейности
времени следует k(n)/n -> 0. => k<=c/c_2 n/ln n, т.е. k=O(n/ln n).

Т.е. для k(n), не лежащих в O(n/ln n), нельзя за линейное время отсортировать k
максимальных.

nOkA. Alexey.

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