提问人：Love Cute Shiba 提问时间：9/29/2019 最后编辑：melpomeneLove Cute Shiba 更新时间：9/30/2019 访问量：640
如何在 O（nloglogn） 时间复杂度内对 range[1， logn**logn] 中的 n 个元素进行排序？
How to sort n elements in range[1, logn**logn] within O(nloglogn) time complexity?
问：
我的算法课上有问题。该问题指出：
假设给定一个 n个整数数组，其范围为 {1,...,logn**logn}。显示如何在时间 O（nloglogn） 中对这个数组进行排序。
这是每周的作业，本周我们主要进行堆排序和计数排序。乍一看，我看到有一个范围，所以我试着数了一下......但是范围太大了。计数排序为 O（n+k），其中 k 是范围。此处 logn**logn 大于所需的 nloglogn。所以我感到迷茫。 因此，可以肯定的是，我们不能使用比较排序，因为它的边界低于 O（n logn）。谁能帮忙？
答：
0赞
rcgldr
9/30/2019
#1
假设 n 是一个整数，使得存在一个整数 x，使得 a = logx（n） 和 b = logx（a） = logx（logx（n）） 是整数，那么使用 n 作为基数，时间复杂度 O（n b） = O（n log（log（n）） 将需要 b 基数传递。算一算：
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
评论
0赞
Love Cute Shiba
9/30/2019
嗨，我不明白你是如何计算基数的。假设您使用 n 作为基础。所以我们想知道基数，这样--->n^radix = 范围内的最大数量 = logn 的 logn 的幂。
0赞
Love Cute Shiba
9/30/2019
然后我尝试求解基数。取两边的原木。基数 * n = logn * log_base n_（logn）
0赞
Love Cute Shiba
9/30/2019
但我不明白最后如何想出log（log（n））。谢谢
0赞
rcgldr
10/1/2019
@chicago - 我在数学部分展示了这一点。 a = logx（n）。b = logx（logx（n）） = logx（a） = 基数走刀数。然后在数学部分的最后一行，我展示了范围 （max+1-min） = n^b = ... = a^a = logx（n）^logx（n）。因此，当 b = logx（logx（n）） 基数传递时，每个基数传递移动 n 个元素，时间复杂度为 O（n log（log（n）））。
评论