基数排序解释
Radix sort explanation
基于这篇基数排序文章http://www.geeksforgeeks.org/radix-sort/我很难理解根据排序中某些方法的时间复杂度所解释的内容。
来自link：
设输入整数有d位。 Radix Sort 需要 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 个元素，但我从那里丢失了它。一个简单的解释会很有帮助。
假设我们使用桶排序对每个数字进行排序：对于每个数字 (d)，我们处理所有数字 (n)，将它们放入桶中以获得一个数字可能具有的所有可能值 (b).
然后我们需要处理所有的桶，重新创建原始列表。将所有项目放入桶中需要 O(n) 时间，从所有桶中重新创建列表需要 O(n + b) 时间（我们必须遍历所有桶和其中的所有元素），我们对所有数字都这样做, 给出 运行 时间 O(d * (n + b)).
如果 d 是常数且 b 不渐近地大于 n，则这 仅 线性。所以确实，如果你有 log n 位的数字，它将花费 O(n log n) 时间。
基于这篇基数排序文章http://www.geeksforgeeks.org/radix-sort/我很难理解根据排序中某些方法的时间复杂度所解释的内容。
来自link：
设输入整数有d位。 Radix Sort 需要 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 个元素，但我从那里丢失了它。一个简单的解释会很有帮助。
假设我们使用桶排序对每个数字进行排序：对于每个数字 (d)，我们处理所有数字 (n)，将它们放入桶中以获得一个数字可能具有的所有可能值 (b).
然后我们需要处理所有的桶，重新创建原始列表。将所有项目放入桶中需要 O(n) 时间，从所有桶中重新创建列表需要 O(n + b) 时间（我们必须遍历所有桶和其中的所有元素），我们对所有数字都这样做, 给出 运行 时间 O(d * (n + b)).
如果 d 是常数且 b 不渐近地大于 n，则这 仅 线性。所以确实，如果你有 log n 位的数字，它将花费 O(n log n) 时间。