|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Gimpelson Vadik 2:5020/400 16 Sep 2002 05:06:44
To : Roman Kukushkin
Subject : Re: сортировка с линейной сложностью
--------------------------------------------------------------------------------
>
> SA>>>>> Сортировка с линейной сложностью возможна лишь в случае, когда
> SA>>>>> данные могут принимать конечное число значений.
> RK>>>> А доказательства есть?
>
> SA>>> Hа самом деле в моей фразе содержится два утверждения.
> SA>>> Доказательство какого из них тебя интересует?
>
> RK>> "Сортировка с линейной сложностью невозможна для некоторых
> RK>> вероятностных источников, использующих постоянный закон
> RK>> распределения." Это явно частный случай твоего утверждения. Если
> RK>> можешь обобщить - будет еще интереснее, т.к будет
> RK>> неожиданней. Т.е. для массива данных, представляющих собой исходы
> RK>> экспериментов с одинаковым для всех опытов, известным (заранее
> RK>> заданным) законом распределения требуется провести сортировку. Я
> RK>> думаю, что количество операций для сортировки такого массива из n
> RK>> элементов будет составлять O(n) операций. Мне интересно будет
> RK>> увидеть доказательство или опровержение этого факта.
>
> SA> Ты пишешь об исходах экспериментов и ничего не пишешь о том, какова
> SA> природа получаемых в результате эксперимента данных. Hапример, если
> 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
