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

From

Gimpelson Vadik ()

To

Roman Kukushkin

Date

2002-09-16T05:06:44Z

Area

RU.ALGORITHMS

From: "Gimpelson Vadik" <zca187@sectorb.msk.ru>

>
>  SA>>>>> Сортировка с линейной сложностью возможна лишь в случае, когда
>  SA>>>>> данные могут принимать конечное число значений.
>  RK>>>> А доказательства есть?
>
>  SA>>> На самом деле в моей фразе содержится два утверждения.
>  SA>>> Доказательство какого из них тебя интересует?
>
>  RK>> "Сортировка с линейной сложностью невозможна для некоторых
>  RK>> вероятностных источников, использующих постоянный закон
>  RK>> распределения." Это явно частный случай твоего утверждения. Если
>  RK>> можешь обобщить - будет еще интереснее, т.к будет
>  RK>> неожиданней. Т.е. для массива данных, представляющих собой исходы
>  RK>> экспериментов с одинаковым для всех опытов, известным (заранее
>  RK>> заданным) законом распределения требуется провести сортировку. Я
>  RK>> думаю, что количество операций для сортировки такого массива из n
>  RK>> элементов будет составлять O(n) операций. Мне интересно будет
>  RK>> увидеть доказательство или опровержение этого факта.
>
>  SA>   Ты пишешь об исходах экспериментов и ничего не пишешь о том, какова
>  SA> природа получаемых в результате эксперимента данных. Например, если
>  SA> результа бросания монеты - два состояния: орел или решка, то
очевидно,
>  SA> что для сортировки подобных исходов хватит и линейного количества
>  SA> операций. Если же исход - вещественное число, думаю, меньше чем
>  SA> n*log(n) не обойтись. Kстати, если _ты_ думаешь, что достаточно O(n)
>  SA> операций, то _тебе_ это и доказывать.
> Тогда что означает подчеркнутая выше фраза? Просто любопытство? Я
воспринял ее
> как готовность доказать оба этих утверждения. А я сразу честно признался,
что
> доказательства я не знаю, а самому мне лень.
> Вообще-то я думаю, что возможность сортировки за O(n) уже давно доказана,
хотя
> на 100% не уверен. Может быть кто-то знает?
>
>                 C уважением, Roman Kukushkin.
>

О какой сложности идёт речь: о средней или  в худшем случае?
Боюсь что в худшем ничего лучше nlogn не получить. А со средней ещё надо
покрутить.
                    Vadik


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)