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

From

Oleg V.Cat (2:5100/80)

To

Gimpelson Vadim

Date

2002-09-16T13:47:45Z

Area

RU.ALGORITHMS

Hello Gimpelson!

Monday September 16 2002, Gimpelson Vadim writes to Anthone Tikhonov:

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

\____Cat
/\  /\

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