algorithm - 基数排序解释

Question

基于这篇基数排序文章http://www.geeksforgeeks.org/radix-sort/我正在努力理解在排序中某些方法的时间复杂度方面所解释的内容。

从链接：

假设输入整数中有 d 个数字。基数排序需要 O(d*(n+b)) 时间，其中 b 是表示数字的基数，例如对于十进制系统，b 是 10。d 的值是多少？如果 k 是最大可能值，则 d 将为 O(log_b(k))。所以整体时间复杂度是 O((n+b)*logb(k))。这看起来比基于比较的大 k 排序算法的时间复杂度要高。让我们首先限制k。令 k≤nc 其中 c 是一个常数。在这种情况下，复杂度变为 O(nlogb(n))。

所以我明白排序需要 O(d*n) 因为有 d 位因此 d 传递，你必须处理所有 n 元素，但我从那里丢失了它。一个简单的解释将非常有帮助。

Answer 1

假设我们使用桶排序对每个数字进行排序：对于每个数字(d)，我们处理所有数字(n)，将它们放入桶中以获取数字可能具有的所有可能值(b)。

然后我们需要处理所有的桶，重新创建原始列表。将所有项目放入桶中需要O(n)时间，从所有桶中重新创建列表需要O(n + b)时间（我们必须遍历所有桶和其中的所有元素），并且我们对所有数字执行此操作，运行时间为O(d * (n + b)).

这仅是线性的，如果d是一个常数并且b不是渐近大于 的n。因此，确实，如果您有很多log n位数，那将需要O(n log n)时间。