|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roman Kukushkin 2:5025/37.216 11 Aug 2002 23:20:55
To : Sergey Andrianov
Subject : сортировка с линейной сложностью
--------------------------------------------------------------------------------
Пятница Август 09 2002 в 23:38 Sergey Andrianov писал Roman Kukushkin:
SA>>> Сортировка с линейной сложностью возможна лишь в случае, когда
SA>>> данные могут принимать конечное число значений.
RK>> А доказательства есть?
SA> Hа самом деле в моей фразе содержится два утверждения.
SA> Доказательство какого из них тебя интересует?
"Сортировка с линейной сложностью невозможна для некоторых вероятностных
источников, использующих постоянный закон распределения."
Это явно частный случай твоего утверждения. Если можешь обобщить - будет еще
интереснее, т.к будет неожиданней.
Т.е. для массива данных, представляющих собой исходы экспериментов с одинаковым
для всех опытов, известным (заранее заданным) законом распределения требуется
провести сортировку. Я думаю, что количество операций для сортировки такого
массива из n элементов будет составлять O(n) операций. Мне интересно будет
увидеть доказательство или опровержение этого факта.
C уважением, Roman Kukushkin.
E-mail krv@vudor.vrn.ru
---
* Origin: (2:5025/37.216)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
