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

From

Anthone Tikhonov ()

To

Gimpelson Vadik

Date

2002-09-16T12:51:24Z

Area

RU.ALGORITHMS

From: "Anthone Tikhonov" <ia26@vtb.ru>

 GV> О какой сложности идёт речь: о средней или  в худшем случае?
 GV> Боюсь что в худшем ничего лучше nlogn не получить. А со средней ещё надо
 GV> покрутить.

Если мы сортируем данные, полученные случайным образом, фраза "в худшем
случае" не подходит, т.к. алгоритм, применимый для худшего случая, применим
также и для любого произвольно заданного набора данных, который, понятно, за
линейное время не отсортируешь
Если же все-таки считать, что набор случаен и распределен равномерно, то можно
написать алгоритм, который, скажем, в 99.995 % случаев будет работать за
линейное время

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)