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

From

Stepan M. Pechkin (2:5030/1688.11)

To

Alexey Kruglov

Date

2002-08-16T14:11Z

Area

RU.ALGORITHMS

O, Alexey!

Monday August 12 2002 22:33, Alexey Kruglov wrote to Stepan M Pechkin:

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

 AK> Никто, вроде, не ответил, так что отвечу.

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

    Это, простите, как?

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

    А разве не за O(1)?
    Что мы называем кучей? Реализацию бинарного дерева поиска через массив? И
что, мы не можем найти крайний элемент массива за O(1)?

 AK>  => при k=ln(n) это все будет работать за O(n+k ln
 AK> n)=O(n).

    А каким образом O(n lg n) = O(n)?

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

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

    Спасибо, это все я читал. Видимо, понял не так, как ты.

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

        Stepan (-: с приветом :-)

tmpechkin@hotmail.com                   http://pechkin.rinet.ru
                                        ICQ#21296772

---
 * Origin: >*< Осенизатор бытовой. (FidoNet 2:5030/1688.11)