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

From

Dmitriy K. ()

To

Roman Kukushkin

Date

2002-08-05T16:39:26Z

Area

RU.ALGORITHMS

From: "Dmitriy K." <krylov@mail.primorye.ru>

Привет, Roman!
Thu, 01 Aug 2002 19:54:36 +0400 Вы написали to Dmitriy K.:

 RK> 3) для каждого сегмента выполняем сортировку любым методом;
                                       ^^^^^^^^^^

Любым? Чтобы линейность оставалась для всего, на этом шаге также должна быть
линейность.
Опять приходим к поиску линейного алгоритма. Если же рекурсивно - то
получается опять же нелинейно (кажется, N*log(n) - в книжке об этом
подробнее написано).


 DK>> Зависит от того, что за "данные" и что за "величина".
 RK> Внимательнее читай текст письма, на которое отвечаешь.

Ну и что же я упустил? Фраза "случайная величина с равномерным
распределением" в исходном письме ничего не говорит ни о структуре самих
данных, ни о подходящем и выбранном программистом типе данных. Это может
быть и целое число, представляемое типами от byte до int64, или
действительное, представляемое теми же float, double, а при особой
изворотливости и целочисленными типами, или строка какая-нибудь... Так что,
как говориться, "Внимательнее читай текст письма, на которое отвечаешь".

 DK>> P.P.S. В инете проскакивала как-то информация о O(log(log(log(n))))
 DK>> сортировке... Типа, для больших n ;) . Могу поискать на винте.
 RK> Не верю. Чтобы отсортировать массив, нужно хотя бы посмотреть на
 RK> каждое число, что дает ассимптотику не лучше O(n)

Да, я ошибся. Я посмотрел формулу - автор утверждает, что сложность -
O(n(log(log(n)))).
Статьи по этому поводу у меня нет, есть только исходник. Я с ним не
разбирался, поверил автору на слово :). Ссылка вот:
http://www.nada.kth.se/~snilsson, могу выслать этот исходник.

Удачи!
__________________________________________________________________________
--{ Dmitriy Krylov aka "Abulafia"   }-------------------------------------
--{ mailto: krylov@mail.primorye.ru }-------------------------------------



-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)