|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stepan M. Pechkin 2:5030/1688.11 16 Aug 2002 14:11:00
To : Alexey Kruglov
Subject : выборка из несортированного списка
--------------------------------------------------------------------------------
Monday August 12 2002 22:33, Alexey Kruglov wrote to Stepan M Pechkin:
SP>> Дан несортированный список длиной n. Из него нужно выбрать _по
SP>> порядку_ lg(n) максимальных элементов за количество операций, линейное
SP>> от n. Второй вопрос: насколько можно увеличить количество выбираемых
SP>> по порядку максимальных, чтобы все еще укладываться в линейное время?
AK> Hикто, вроде, не ответил, так что отвечу.
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> Алгоритмы: построение и анализ. М.: МЦHМО, 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. Hетрудно подсчитать, что в O(n)
укладывается.
Все это выглядит так просто, когда уже решено...
Stepan (-: с приветом :-)
tmpechkin@hotmail.com http://pechkin.rinet.ru
ICQ#21296772
---
* Origin: >*< Осенизатор бытовой. (FidoNet 2:5030/1688.11)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
