|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Gimpelson Vadim 2:5020/400 18 Sep 2002 15:08:07
To : Sergey Andrianov
Subject : Re: сортировка с линейной сложностью
--------------------------------------------------------------------------------
> Здравствуй, 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>> Hа самом деле в моей фразе содержится два утверждения.
> SA>> Доказательство какого из них тебя интересует?
> RK> "Сортировка с линейной сложностью невозможна для некоторых
вероятностных
> RK> источников, использующих постоянный закон распределения."
> RK> Это явно частный случай твоего утверждения. Если можешь обобщить -
будет
> RK> еще интереснее, т.к будет неожиданней.
> RK> Т.е. для массива данных, представляющих собой исходы экспериментов с
> RK> одинаковым для всех опытов, известным (заранее заданным) законом
> RK> распределения требуется провести сортировку. Я думаю, что количество
> RK> операций для сортировки такого массива из n элементов будет составлять
> RK> O(n) операций. Мне интересно будет увидеть доказательство или
опровержение
> RK> этого факта.
>
> Ты пишешь об исходах экспериментов и ничего не пишешь о том, какова
природа
> получаемых в результате эксперимента данных. Hапример, если результа
бросания
> монеты - два состояния: орел или решка, то очевидно, что для сортировки
> подобных исходов хватит и линейного количества операций. Если же исход -
> вещественное число, думаю, меньше чем n*log(n) не обойтись.
> Kстати, если _ты_ думаешь, что достаточно O(n) операций, то _тебе_ это и
> доказывать.
>
> До свидания, в 19:59 MSK
> Sergey
Привет all.
Предлагаю следующий алгоритм.
Пусть у нас есть некоторый вероятностный источник с равномерным
распределением
на [0,1]. Hадо отсортировать 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
