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

From

Gimpelson Vadim ()

To

Anthone Tikhonov

Date

2002-09-16T14:13:22Z

Area

RU.ALGORITHMS

From: "Gimpelson Vadim" <zca187@sectorb.msk.ru>

"Anthone Tikhonov" <ia26@vtb.ru> wrote in message
news:am46qc$d9i$2137@www.fido-online.com...
> GV> О какой сложности идёт речь: о средней или  в худшем случае?
>  GV> Боюсь что в худшем ничего лучше nlogn не получить. А со средней ещё
надо
>  GV> покрутить.
>
> Если мы сортируем данные, полученные случайным образом, фраза "в худшем
> случае" не подходит, т.к. алгоритм, применимый для худшего случая,
применим
> также и для любого произвольно заданного набора данных, который, понятно,
за
> линейное время не отсортируешь
> Если же все-таки считать, что набор случаен и распределен равномерно, то
можно
> написать алгоритм, который, скажем, в 99.995 % случаев будет работать за
> линейное время
>
Может быть можно построить алгоритм который в среднем сортирует за n, а
худшем за n^3?И может такой алгоритм нам не подходит... Так что про
сложность в худшем случае тоже имеет смысл говорить.
Vadik.


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)