|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg V.Cat 2:5100/80 29 Sep 2002 11:21:39
To : Nickita A Startcev
Subject : сортировка с линейной сложностью
--------------------------------------------------------------------------------
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> бывает редко...
Hу тут уже постулиpовать надо, что и как считается отсоpтиpованным :-). И только
в том случае, если все ключи pазные. А так можно хоть пузыpёк взять - в лучшем
случае у него тоже O(N). А в худшем - всего-то N^2.
NAS> . С уважением,
NAS> Hикита.
NAS> -+- GoldED+/LNX 1.1.4.7
NAS> + Origin: Люди Билли не любили... (c) (2:5030/1039.8)
\____Cat
/\ /\
---
* Origin: CatMare (2:5100/80)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
