|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nickita A Startcev 2:5030/1039.8 28 Sep 2002 02:22:48
To : Oleg V.Cat
Subject : сортировка с линейной сложностью
--------------------------------------------------------------------------------
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) памяти бывает редко...
. С уважением, Hикита.
--- GoldED+/LNX 1.1.4.7
* Origin: Люди Билли не любили... (c) (2:5030/1039.8)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
