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

From

Vladimir A. Pertzel ()

To

Ilya Teterin

Date

2002-08-04T16:41:44Z

Area

RU.ALGORITHMS

From: "Vladimir A. Pertzel" <voldemar@relhum.org>


"Ilya Teterin" <alien@npp-integris.ru> wrote in message
news:8JO19.81$i_4.7353@news.rt.ru!rt.ru...

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

Да. Для случайной величины с заранее известной функцией
распределения и заранее известным объемом выборки существует
алгоритм, позволяющий отсортировать ее за линейное время,
если рассматривать сложность "в среднем".

Пусть объем выборки равен N. Разбиваем область значений
на N сегментов так, что мат.ожидание числа значений,
попавших в сегмент равно единице (при равномерном распре-
делении просто делим интервал не N частей). Число значений
сл. величины, попавших в некоторый интервал есть другая
случайная величина, распределенная по закону Пуассона,
и потому, имеющая конечный второй момент, следовательно,
в каждом интервале мы можем пузырьковой сортировкой
отсортировать попавшие в него значения за время, имеющее
конечное мат.ожидание. Помножив эту конечную величину на
число интервалов, получим O(N). После этого, последовательно
собрав значения из всех интервалов за O(N), за линейное
время получим отсортированную последовательность.

Если распределение случайной величины X не равномерное,
то вычислив значение функции распределения вероятностей Y=F(X)
получим величину Y, равномерно распределенную, а F(X) назовем
словом "функция хэширования"

--- ifmail v.2.15dev5
 * Origin: Sent via Graf's Inn at news://news.relhum.org (2:5020/400)