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

From

Anthone Tikhonov ()

To

Ilya Teterin

Date

2002-08-20T14:24:48Z

Area

RU.ALGORITHMS

From: ia26@vtb.ru (Anthone Tikhonov)

> Существует ли алгоритм сортировки с линейной вычислительной сложностью, если
> известно, что сортируемые данные - случайная величина с равномерным
> распределением?

Была же статья, Vladimir A. Pertzel и Pertzel Family, я с ними
полностью согласен. Можно разбить торезок даже не на N сегментов, а на
2*N, тогда вероятность попадания 2х чисел в 1 сегмент еще меньше

Почему ты говоришь, что пли малейшем отклонении от равномерности
вылезает логарифм? Можно доказать, что для любого N, если
распределение действительно равномерное, вероятность того, что
сложность сортировки превысит, скажем, 10*N, будет не более какого-то
порога типа 0.0001, или посчитать мат. ожидание сложности сортировки -
оно будет линейной величиной от N
--- ifmail v.2.15dev5
 * Origin: http://groups.google.com/ (2:5020/400)