|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Gimpelson Vadim 2:5020/400 16 Sep 2002 14:05:11
To : Anthone Tikhonov
Subject : Re: сортировка с линейной сложностью
--------------------------------------------------------------------------------
"Anthone Tikhonov" <ia26@vtb.ru> wrote in message
news:am46qc$d9i$2137@www.fido-online.com...
> GV> О какой сложности идёт речь: о средней или в худшем случае?
> GV> Боюсь что в худшем ничего лучше nlogn не получить. А со средней ещё
надо
> GV> покрутить.
>
> Если мы сортируем данные, полученные случайным образом, фраза "в худшем
> случае" не подходит, т.к. алгоритм, применимый для худшего случая,
применим
> также и для любого произвольно заданного набора данных, который, понятно,
за
> линейное время не отсортируешь
> Если же все-таки считать, что набор случаен и распределен равномерно, то
можно
> написать алгоритм, который, скажем, в 99.995 % случаев будет работать за
> линейное время
>
А мат ожидание времени линейно будет?
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
