|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roman Kukushkin 2:5025/37.216 01 Aug 2002 20:54:36
To : Dmitriy K.
Subject : сортировка с линейной сложностью
--------------------------------------------------------------------------------
Среда Июль 31 2002 в 18:20 Dmitriy K. писал Ilya Teterin:
IT>> Существует ли алгоритм сортировки с линейной вычислительной
IT>> сложностью, если известно, что сортируемые данные - случайная
IT>> величина с равномерным распределением?
DK> Существует. Hо человечеству пока не известна ;-)
Hу, так уж и не известна? Может попробовать стать знаменитым ;) ... А у Кнута
смотреть не пробовали?
В общем идею могу предложить такую:
1) отрезок распределения делится на равные по длине сегменты общим числом равным
числу сортируемых данных (или можно в конечное число раз меньше);
2) за один проход раскидываем все сортируемые числа по сегментам;
3) для каждого сегмента выполняем сортировку любым методом;
4) склеиваем получившиеся сегменты.
Пункты 1,2,4 точно не сложнее линейного. Пункт 3 скорей всего линейный (так мне
подсказывает моя интуиция, если кто не верит, можно проверить, подсчитав мат.
ожидание числа действий.
DK> Зависит от того, что за "данные" и что за "величина".
Внимательнее читай текст письма, на которое отвечаешь.
DK> P.P.S. В инете проскакивала как-то информация о O(log(log(log(n))))
DK> сортировке... Типа, для больших n ;) . Могу поискать на винте.
Hе верю. Чтобы отсортировать массив, нужно хотя бы посмотреть на каждое число,
что дает ассимптотику не лучше O(n)
C уважением, Roman Kukushkin.
E-mail krv@vudor.vrn.ru
---
* Origin: (2:5025/37.216)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
