algorithm - 基数排序 nx (k/d) 的解释

Question

我查看了基数排序算法的最佳、平均和最坏情况时间。

平均值为 NXK/D

我知道 N 是算法中的元素数

我知道 K 是键/桶的数量

有谁知道D代表什么？

我要去维基百科上的桌子，谢谢

参考 - http://en.wikipedia.org/wiki/Sorting_algorithm#Radix_sort

Answer 1

D是 base 中的位数K。

例如，如果您有 K = 16，并且最大数是255，D = 2 (16 ^ 2 = 256)。如果更改K为 4 ，则D变为 4 (4 ^ 4 = 256)。

Answer 2

基数排序的运行时间通常简化为 O(n)，但有几个因素会导致此运行时间急剧增加。

分配变量：

n =要排序的元素数/n

L = 元素的长度，也就是每个元素的位数

k = 每个元素中的数字范围（数字范围从 1 到 k）

基数排序算法对每个元素中的每个数字执行桶排序。因此，必须进行 L 次排序，并且每次排序需要 O(n+k) 时间，因为它是将 n 个元素放入 k 个桶中的桶排序。因此，基数排序更准确的运行时间是 O(L(n+k))。

当数字范围 k 是一个小常数时，如十进制数，则基数排序的运行时间可以简化为 O(Ln)。

由于这些因素会影响基数排序算法的运行时间，因此需要考虑使用该算法按顺序执行排序或使其高效。数据需要：

1. 具有固定长度（可以选择填充元素以便为所有元素创建统一的长度）
2. 元素的长度 L 在 n 中是线性的
3. 数字范围 k 在 n 中是线性的