Как отсортировать n элементов в диапазоне [1, logn ** logn] в течение O (nloglogn) временной сложности?

Question

У меня проблема в классе алгоритмов.Проблема гласит:

Предположим, вам дан массив из n целых чисел в диапазоне {1, ..., logn ** logn}.Покажите, как сортировать этот массив по времени O (nloglogn).

Это еженедельное задание, на этой неделе мы в основном работаем над сортировкой кучи и сортировкой подсчета.Ну, с первого взгляда я вижу, что есть диапазон, поэтому я попытался считать сортировку .... Но диапазон слишком велик.Отсчетом сортировки является O (n + k), где k - диапазон.Здесь logn ** logn больше требуемого nloglogn.Поэтому я чувствую себя потерянным.Так что, конечно, мы не можем использовать сортировку сравнения, потому что она ограничена ниже O (n logn).Кто-нибудь может помочь?

Answer 1

Предполагая, что n является целым числом, таким, что существует целое число x , таким, что a = logx ( n ) и b = logx ( a ) = logx (logx ( n )) являются целыми числами, тогда, используя n в качестве основания радиуса, оно будетпринять b радикальных проходов для сложности времени O (nb) = O (n log (log (n)). Делаем математику:

x^a = n
x^b = a
a^a = range
n^b = range of radix sort
n^b = (x^a)^b = x^(a b) = x^(a logx(a)) = x^(logx(a^a)) = a^a

пример

n = 65536
x = 2
a = 16
b = 4
2^16 = n
2^4 = 16
a^a = range = 2^64
n^b = range of radix sort = (2^16)^4 = 2^(16 · 4) = 2^64