|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy K. 2:5020/400 05 Aug 2002 16:39:26
To : Ilya Teterin
Subject : Re: сортировка с линейной сложностью
--------------------------------------------------------------------------------
Привет, Ilya!
Wed, 31 Jul 2002 15:34:30 +0000 (UTC) Вы написали to Dmitriy K.:
IT> Хай, Дмитрий!
Воистину хай!
IT> "Dmitriy K." <krylov@mail.primorye.ru>
IT> <skipped>
IT> Спасибо за ответ. Жаль, линейная сортировка нескольких миллионов
IT> 160-ти разрядной информации по указанному алгоритму не получится -
IT> если выделять старшие разряды, опять получится этот противный
IT> N*log(n) ;)
Хм... Пусть есть исходная последовательность. Сначала сортируем по первому
байту, потом - по второму, и т.д. до 20-го байта (элемент 160-разрядный,
если "разряд" - это бит, то имеем 20 битов). Сортировка исходной
последовательности по первому байту аналогична разбиению её на 256 кусков,
по второму - 256*256 кусков и т.д.. Т.к. шаг сортировки - линейный - то
получается:
Сортировка по 1-ому байт требует O(N) действий
Сортировка по 2-ому байт требует 256 * O(N') действий (отсортировать линейно
256 кусков)
Сортировка по 3-ему байт требует 256 * 256 * O(N'') действий
Сортировка по 4-ому байт требует 256 * 256 * 256 * O(N''') действий
...
Сортировка по 20-ому байт требует 256 ^ (20-1) * O(N'''...'') действий
начиная с 2-го байта N - проштрихованы, и означают длину самой длиной
подпоследовательности.
Т.к. последовательность разделяется на куски, то каждый кусок _может_
содержать меньшее количество элементов. Hо в худшем случае придется
сортировать всю последовательность... Так что N <= N' <= N'' <= N''' <= ...
<= N'''...''
Так как процесс итеративный и зависит от длины числа, то общая сложность:
O(n) + 256*O(N') + 256*256*O(N'') + ... + 256^20*O(N'''...'') действий.
Апроксимируется __O(N)__.
То есть алгоритм - линейный :-). Hо! Из-за __большого__ множителя (~10^50)
эффективен будет, наверное, только для оооочень длиных последовательностей.
Hо! Я не учел сокращения последовательности. Т.к. она на поздних шагах
всё-таки будет дробиться (т.е. N'''...'' <= N'''...'''), то коэффициент
перед последними слагаемыми будет поменьше. К сожалению, мозгов не хватает
посчитать более строго. Возможно, я ошибся - как в положительную, так и в
отрицательную стороны.
===
А реализовать можно так: взять ту же карманную сортировку (или как там её,
из предыдущего моего письма), и несколько модифицировать - сделать не массив
счетчиков, а массив указателей. Если при первом проходе встречается число с
некоторым байтом, то добавляем указатель на это число к массиву указателей
по этому байту. Тут фишка в организации данных - чтобы это добавление,
проход по этим указателям и т.д. были также линейными.
===
Кстати, а сортировать с нуля нужно? Или добавить очередной элемент? Или
последовательность "хоть немного" отстортирована?
Удачи!
__________________________________________________________________________
--{ 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
