algorithm - 如何在 O(nloglogn) 时间复杂度内对 range[1, logn**logn] 中的 n 个元素进行排序？

Question

我的算法课有问题。问题状态:

Assume you are given an array of n integers in the range{1,...,logn**logn}. Show how to sort this array in time 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 作为基数，时间复杂度为 O(n b) = 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