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

From

Nickita A Startcev (2:5030/1039.8)

To

Oleg V.Cat

Date

2002-09-28T02:22:48Z

Area

RU.ALGORITHMS

Привет, Oleg !


 16 Sep 02 , 13:47  Oleg V.Cat писал к Gimpelson Vadim:

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

Если у нас есть 2^(2^N) ячеек паямяти, где N-количество разрядов в сортируемых данных - то можно и за линейное время, но 2^(2^N) памяти бывает редко...

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