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

From

Dmitriy K. ()

To

Ilya Teterin

Date

2002-08-05T16:39:26Z

Area

RU.ALGORITHMS

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

Привет, 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 - проштрихованы, и означают длину самой длиной
подпоследовательности.
Т.к. последовательность разделяется на куски, то каждый кусок _может_
содержать меньшее количество элементов. Но в худшем случае придется
сортировать всю последовательность... Так что N <= N' <= N'' <= N''' <= ...
<= N'''...''

Так как процесс итеративный и зависит от длины числа, то общая сложность:
O(n) + 256*O(N') + 256*256*O(N'') + ... + 256^20*O(N'''...'') действий.
Апроксимируется __O(N)__.

То есть алгоритм - линейный :-). Но! Из-за __большого__ множителя (~10^50)
эффективен будет, наверное, только для оооочень длиных последовательностей.

Но! Я не учел сокращения последовательности. Т.к. она на поздних шагах
всё-таки будет дробиться (т.е. 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)