|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy K. 2:5020/400 05 Aug 2002 16:39:26
To : Roman Kukushkin
Subject : Re: сортировка с линейной сложностью
--------------------------------------------------------------------------------
Привет, Roman!
Thu, 01 Aug 2002 19:54:36 +0400 Вы написали to Dmitriy K.:
RK> 3) для каждого сегмента выполняем сортировку любым методом;
^^^^^^^^^^
Любым? Чтобы линейность оставалась для всего, на этом шаге также должна быть
линейность.
Опять приходим к поиску линейного алгоритма. Если же рекурсивно - то
получается опять же нелинейно (кажется, N*log(n) - в книжке об этом
подробнее написано).
DK>> Зависит от того, что за "данные" и что за "величина".
RK> Внимательнее читай текст письма, на которое отвечаешь.
Hу и что же я упустил? Фраза "случайная величина с равномерным
распределением" в исходном письме ничего не говорит ни о структуре самих
данных, ни о подходящем и выбранном программистом типе данных. Это может
быть и целое число, представляемое типами от byte до int64, или
действительное, представляемое теми же float, double, а при особой
изворотливости и целочисленными типами, или строка какая-нибудь... Так что,
как говориться, "Внимательнее читай текст письма, на которое отвечаешь".
DK>> P.P.S. В инете проскакивала как-то информация о O(log(log(log(n))))
DK>> сортировке... Типа, для больших n ;) . Могу поискать на винте.
RK> Hе верю. Чтобы отсортировать массив, нужно хотя бы посмотреть на
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
