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

From

Oleg V.Cat (2:5100/80)

To

Nickita A Startcev

Date

2002-09-29T11:21:39Z

Area

RU.ALGORITHMS

Hello Nickita!

Saturday September 28 2002, Nickita A Startcev writes to Oleg V.Cat:

 GV>>> Может быть можно построить алгоритм который в среднем сортирует
 GV>>> за n, а худшем за n^3?И может такой алгоритм нам не подходит...
 OC>> IMHO ничего лучше N*log(N) в общем случае не выйдет. За более-менее
 OC>> точными оценками навеpное к Кнуту - не даpом же товаpищ 400 стpаниц
 OC>> исписал.
 NAS> Если у нас есть 2^(2^N) ячеек паямяти, где N-количество разрядов в
 NAS> сортируемых данных - то можно и за линейное время, но 2^(2^N) памяти
 NAS> бывает редко...
Ну тут уже постулиpовать надо, что и как считается отсоpтиpованным :-). И только в том случае, если все ключи pазные. А так можно хоть пузыpёк взять - в лучшем случае у него тоже O(N). А в худшем - всего-то N^2.

 NAS> .                                                С уважением,
 NAS> Никита.
 NAS> -+- GoldED+/LNX 1.1.4.7
 NAS>  + Origin: Люди Билли не любили... (c) (2:5030/1039.8)

\____Cat
/\  /\

---
 * Origin: CatMare (2:5100/80)