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