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

From

Stepan M. Pechkin (2:5030/1688.11)

To

All

Date

2002-07-30T22:36Z

Area

RU.ALGORITHMS

* Crossposted in PECHKIN.SPEAKS
* Crossposted in RU.ALGORITHMS

O, All!

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

    Ничего не приходит в голову.

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

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

---
 * Origin: >*< Ассоциация Анонимных Ирландцев (FidoNet 2:5030/1688.11)