|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 27 Aug 2002 20:03:34
To : Roman Kukushkin
Subject : Re: сортировка с линейной сложностью
--------------------------------------------------------------------------------
Однажды 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>> Hа самом деле в моей фразе содержится два утверждения.
SA>> Доказательство какого из них тебя интересует?
RK> "Сортировка с линейной сложностью невозможна для некоторых вероятностных
RK> источников, использующих постоянный закон распределения."
RK> Это явно частный случай твоего утверждения. Если можешь обобщить - будет
RK> еще интереснее, т.к будет неожиданней.
RK> Т.е. для массива данных, представляющих собой исходы экспериментов с
RK> одинаковым для всех опытов, известным (заранее заданным) законом
RK> распределения требуется провести сортировку. Я думаю, что количество
RK> операций для сортировки такого массива из n элементов будет составлять
RK> O(n) операций. Мне интересно будет увидеть доказательство или опровержение
RK> этого факта.
Ты пишешь об исходах экспериментов и ничего не пишешь о том, какова природа
получаемых в результате эксперимента данных. Hапример, если результа бросания
монеты - два состояния: орел или решка, то очевидно, что для сортировки подобных
исходов хватит и линейного количества операций. Если же исход - вещественное
число, думаю, меньше чем n*log(n) не обойтись.
Kстати, если _ты_ думаешь, что достаточно O(n) операций, то _тебе_ это и
доказывать.
До свидания, в 19:59 MSK
Sergey
---
* Origin: Sergiev Posad (2:5020/1507.400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
