|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roman Kukushkin 2:5025/37.216 28 Aug 2002 07:12:47
To : Sergey Andrianov
Subject : сортировка с линейной сложностью
--------------------------------------------------------------------------------
Вторник Август 27 2002 в 20:03 Sergey Andrianov писал Roman Kukushkin:
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.
---
* Origin: (2:5025/37.216)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
