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

From

Sergey Andrianov (2:5020/1507.400)

To

Roman Kukushkin

Date

2002-08-27T20:03:34Z

Area

RU.ALGORITHMS

Здравствуй, Roman!

Однажды 11-Aug-02  в 23:20   Roman Kukushkin (2:5025/37.216)
написал       Sergey Andrianov    по поводу
-=-   сортировка с линейной сложностью  -=-

RK> Kак поживаете, Sergey ?

RK> Пятница Август 09 2002 в 23:38 Sergey Andrianov писал Roman Kukushkin:

SA>>>> Сортировка с линейной сложностью возможна лишь в случае, когда
SA>>>> данные могут принимать конечное число значений.
RK>>> А доказательства есть?

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

  Ты пишешь об исходах экспериментов и ничего не пишешь о том, какова природа получаемых в результате эксперимента данных. Например, если результа бросания монеты - два состояния: орел или решка, то очевидно, что для сортировки подобных исходов хватит и линейного количества операций. Если же исход - вещественное число, думаю, меньше чем n*log(n) не обойтись.
  Kстати, если _ты_ думаешь, что достаточно O(n) операций, то _тебе_ это и доказывать.

                  До свидания,  в  19:59 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)