сортировка с линейной сложностью
- From
- Roman Kukushkin (2:5025/37.216)
- To
- Sergey Andrianov
- Date
- 2002-08-28T07:12:47Z
- Area
- RU.ALGORITHMS
Как поживаете, Sergey ?
Вторник Август 27 2002 в 20:03 Sergey Andrianov писал Roman Kukushkin:
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.
---
* Origin: (2:5025/37.216)