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

From

Roman Kukushkin (2:5025/37.216)

To

Gimpelson Vadik

Date

2002-09-16T18:58:44Z

Area

RU.ALGORITHMS

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

 Понедельник Сентябрь 16 2002 в 05:06 Gimpelson Vadik писал Roman Kukushkin:


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

 GV> О какой сложности идёт речь: о средней или  в худшем случае?
 GV> Боюсь что в худшем ничего лучше nlogn не получить. А со средней ещё
 GV> надо покрутить.
Я имел в виду средний случай (мат. ожидание числа операций перестановки/сравнения). А в худшем случае асимптотика будет O(n*n), по крайненй мере я алгоритмов, гарантированно дающих лучшую точность не видел.

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

E-mail krv@vudor.vrn.ru

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