Кто-нибудь знаком с Йиджи Хана , линейным пространством, алгоритмом целочисленной сортировки? Этот результат появляется в довольно короткой статье ( Детерминированная сортировка по времени и линейного пространства . J. Alg. 50: 96–105, 2004), которая в основном склеивает множество более ранних результатов с подходящими приспособления. Моя проблема в том, что он написан довольно махнув рукой, не вдаваясь в подробности. Он в значительной степени опирается на предыдущие статьи, среди которых выделяется еще одна статья Хана ( Улучшенная быстрая целочисленная сортировка в линейном пространстве, Информация и вычисления 170 (1): 81–94) написаны во многом в том же стиле. У меня возникают значительные трудности в понимании этих двух документов, особенно в том, как они адаптируются и используют предыдущие результаты. Буду признателен за любую помощь.
Это, конечно, слишком широкий и расплывчатый вопрос, чтобы считать его правильным вопросом, но я надеюсь развить дискуссию по нескольким четко определенным вопросам и ответам.
Для начала, вот мой первый конкретный вопрос. В лемме 2 инфо. Комп. В статье представлен рекурсивный алгоритм времени для нахождения m-го наименьшего целого числа из набора из маленьких целых чисел, упакованных по в слова RAM. В описании алгоритма не упоминается, как обрабатывается базовый случай . В этом случае требуется сделать выбор за времени. Как это может быть сделано?
Ответы:
Мне просто интересно то же самое.
К счастью, мне удалось найти журнальную статью, опубликованную в 2011 году, которая объясняет именно это; более того, вам не нужна подписка для ее просмотра: анализ реализации и эффективности экспоненциальной сортировки деревьев
Я рекомендую прочитать всю статью, чтобы узнать, как ее можно реализовать, и лучше понять ее основную теорию. Также показано, как экспоненциальные деревья складываются с быстрыми сортировками и двоичными деревьями. Вот соответствующий отрывок связан с Ханя время, линейное пространство, число алгоритма сортировкиO(nloglogn) :
[6] Й. Хан, Детерминированная сортировка в O (n log log n) времени и линейном пространстве, 34-й STOC, 2002.
[8] А. Андерссон, Быстрая детерминистическая сортировка и поиск в линейном пространстве, Симпозиум IEEE по основам информатики, 1996.
источник
Я не уверен насчет ответа (не прошел через документ), но я думаю, что это должно помочь. Числа упакованы в одно слово, поэтому операции над одним словом занимают O (1) времени. Если существует, скажем, k чисел из h битов, то размер слова зависит от k, h, который, в свою очередь, также зависит от диапазона чисел. Таким образом, мы используем методы сокращения диапазона, которые могут уменьшить диапазон чисел, так что многие числа могут поместиться в одном слове. Затем, создавая правильные битовые маски, мы можем найти отдельные большие целые числа из более коротких, считая два слова одновременно. Это можно сделать за O (1) раз. (Подсказка: для этого у каждого числа, хранящегося в слове, есть связанный с ним бит флага, а затем мы вычитаем два слова ... если бит флага идет, то это число меньше).
Аналогично, используя вышеизложенное, мы также можем отсортировать любое слово, содержащее k чисел за O (log k) времени (битовая сортировка)
Изменить: Алгоритм сортировки 2k чисел в диапазоне от 0 до m-1, упакованных в слово, где каждое число принимает размер L of = log (m + k) +2.
будет 1: 000000 1: 000000 1: 000000 1: 000000 ....... так, где бит перед двоеточием также называется битом флага, и каждая последовательность имеет длину L бит и повторяется 2k раз в слове K_1 . (Двоеточие только для понимания)K1
(2k-1) (2k-2) .... 1 записано в двоичном виде. Эскиз алгоритма:K2
Повторите для t = log k до 0.
Часть 1 - разделить оригинальное слово Z на два слова A и B.
Пусть T будет получено смещением (позиции L-1-t) влево и И результатом с K 1 . Пусть M = T- (T смещено на L-1 мест).K2 K1
В = Z- (Z & М).
Часть 2
М = М- (М сдвинуто влево на L-1 мест).
MIN = (B & M) ИЛИ (A- (A & M))
MAX = (A & M) ИЛИ (B- (B & M))
Наконец, соответственно ORing MAX и MIN мы возвращаемся Z.
Я дал эскиз, надеюсь, вы можете заполнить необходимые детали.
источник