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

From

Roman Kukushkin (2:5025/37.216)

To

Dmitriy K.

Date

2002-08-01T20:54:36Z

Area

RU.ALGORITHMS

Как поживаете, Dmitriy ?

 Среда Июль 31 2002 в 18:20 Dmitriy K. писал Ilya Teterin:

 IT>> Существует ли алгоритм сортировки с линейной вычислительной
 IT>> сложностью, если известно, что сортируемые данные - случайная
 IT>> величина с равномерным распределением?

 DK> Существует. Но человечеству пока не известна ;-)
Ну, так уж и не известна? Может попробовать стать знаменитым ;) ... А у Кнута смотреть не пробовали?
В общем идею могу предложить такую:
1) отрезок распределения делится на равные по длине сегменты общим числом равным числу сортируемых данных (или можно в конечное число раз меньше);
2) за один проход раскидываем все сортируемые числа по сегментам;
3) для каждого сегмента выполняем сортировку любым методом;
4) склеиваем получившиеся сегменты.
Пункты 1,2,4 точно не сложнее линейного. Пункт 3 скорей всего линейный (так мне подсказывает моя интуиция, если кто не верит, можно проверить, подсчитав мат. ожидание числа действий.


 DK> Зависит от того, что за "данные" и что за "величина".
Внимательнее читай текст письма, на которое отвечаешь.

 DK> P.P.S. В инете проскакивала как-то информация о O(log(log(log(n))))
 DK> сортировке... Типа, для больших n ;) . Могу поискать на винте.
Не верю. Чтобы отсортировать массив, нужно хотя бы посмотреть на каждое число, что дает ассимптотику не лучше O(n)

                C уважением, Roman Kukushkin.

E-mail krv@vudor.vrn.ru

---
 * Origin:  (2:5025/37.216)