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

From

Gimpelson Vadim ()

To

Sergey Andrianov

Date

2002-09-18T15:08:07Z

Area

RU.ALGORITHMS

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

> Здравствуй, Roman!
>
> Однажды 11-Aug-02  в 23:20   Roman Kukushkin (2:5025/37.216)
> написал       Sergey Andrianov    по поводу
> -=-   сортировка с линейной сложностью  -=-
>
> RK> Kак поживаете, Sergey ?
>
> RK> Пятница Август 09 2002 в 23:38 Sergey Andrianov писал Roman Kukushkin:
>
> SA>>>> Сортировка с линейной сложностью возможна лишь в случае, когда
> SA>>>> данные могут принимать конечное число значений.
> RK>>> А доказательства есть?
>
> SA>>    На самом деле в моей фразе содержится два утверждения.
> SA>> Доказательство какого из них тебя интересует?
> RK> "Сортировка с линейной сложностью невозможна для некоторых
вероятностных
> RK> источников, использующих постоянный закон распределения."
> RK> Это явно частный случай твоего утверждения. Если можешь обобщить -
будет
> RK> еще интереснее, т.к будет неожиданней.
> RK> Т.е. для массива данных, представляющих собой исходы экспериментов с
> RK> одинаковым для всех опытов, известным (заранее заданным) законом
> RK> распределения требуется провести сортировку. Я думаю, что количество
> RK> операций для сортировки такого массива из n элементов будет составлять
> RK> O(n) операций. Мне интересно будет увидеть доказательство или
опровержение
> RK> этого факта.
>
>   Ты пишешь об исходах экспериментов и ничего не пишешь о том, какова
природа
> получаемых в результате эксперимента данных. Например, если результа
бросания
> монеты - два состояния: орел или решка, то очевидно, что для сортировки
> подобных исходов хватит и линейного количества операций. Если же исход -
> вещественное число, думаю, меньше чем n*log(n) не обойтись.
>   Kстати, если _ты_ думаешь, что достаточно O(n) операций, то _тебе_ это и
> доказывать.
>
>                   До свидания,  в  19:59 MSK
>                                  Sergey



Привет all.

Предлагаю следующий алгоритм.
Пусть у нас есть некоторый вероятностный источник с равномерным
распределением
на [0,1]. Надо отсортировать n чисел. Делим отрезок на n частей чтобы
вероятность
попасть в каждый равнялась 1/n. Теперь просматриваем подряд все числа.
 Для каждого из них определяем в какой отрезок оно попадает . Потом
сортируем
внутри каждого отрезка за n^2. Посчитаем среднюю сложность сортировки.
Пусть s(k) - случайная вел. равная колву чисел попавших в к-ый отрезок.
Вероятность того что в проивольный отрезок попадёт m чисел равна
C(n,m)(1/n)^m ((n-1)/n)^(n-m).
Ms(k)^2 = \sum(i=0..n)(  i^2*C(n,i)(1/n)^i ((n-1)/n)^(n-i)  ) = считается
явно =... ~  2e^2<15.
ср сложность  =  M(s(1)^2+s(2)^2+...+s(n)^2) = n*2e^2 < 15n.
Получается линейная средняя сложность, если нигде не наврал)).

                            Вадим.








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