|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anthone Tikhonov 2:5020/400 20 Aug 2002 14:24:48
To : Ilya Teterin
Subject : сортировка с линейной сложностью
--------------------------------------------------------------------------------
> Существует ли алгоритм сортировки с линейной вычислительной сложностью, если
> известно, что сортируемые данные - случайная величина с равномерным
> распределением?
Была же статья, 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
