сортировка с линейной сложностью

From

Roman Kukushkin (2:5025/37.216)

To

Sergey Andrianov

Date

2002-08-11T23:20:55Z

Area

RU.ALGORITHMS

Как поживаете, Sergey ?

 Пятница Август 09 2002 в 23:38 Sergey Andrianov писал Roman Kukushkin:

 SA>>> Сортировка с линейной сложностью возможна лишь в случае, когда
 SA>>> данные могут принимать конечное число значений.
 RK>> А доказательства есть?

 SA>    На самом деле в моей фразе содержится два утверждения.
 SA> Доказательство какого из них тебя интересует?
"Сортировка с линейной сложностью невозможна для некоторых вероятностных источников, использующих постоянный закон распределения."
Это явно частный случай твоего утверждения. Если можешь обобщить - будет еще интереснее, т.к будет неожиданней.
Т.е. для массива данных, представляющих собой исходы экспериментов с одинаковым для всех опытов, известным (заранее заданным) законом распределения требуется провести сортировку. Я думаю, что количество операций для сортировки такого массива из n элементов будет составлять O(n) операций. Мне интересно будет увидеть доказательство или опровержение этого факта.

                C уважением, Roman Kukushkin.

E-mail krv@vudor.vrn.ru

---
 * Origin:  (2:5025/37.216)