基排序的性能特性

Question

我正在阅读C++中Robert算法中基排序的性能特性。在这里，作者在10.6节中提到如下：

下面的链接是在线参考。

QtjhG7WR3IbWtGtA&hl=en&sa=X&ei=sGq9Up69NseprAfx2IG4BA&ved=0CFAQ6AEwBg#v=onepage&q=performance%20characteristics%20of%20radix%20sorts&f=false

LSD基排序用w字节键排序N个记录的运行时间与Nw成正比，因为该算法使w遍历所有N个键。此分析不依赖于输入。 对于长键和短字节，这个运行时间相当于N个lg N:例如，如果我们使用二进制LSD基排序来排序10亿32位键，那么w和lg N都是32。对于较短的键和较长的字节，此运行时间可与N相比:例如，如果在64位键上使用16位基，则w为4，这是一个小常数。

我对上述案文的提问

1. 为什么作者在长键和短字节上与N lg N比较？作者是如何到这里来的，这里w和lg N都是32？
2. 为什么作者与N相比键更短，字节更长？这里的w是如何计算的？
3. 我不明白作者所说的短字节和长字节是什么意思？

Answer 1

1. 他试图用标准表示法(nlogn比wN更容易想象)来表示基类的复杂性。长键和短字节只是使用基排序的可能情况之一，因此这是一个例子(在不同的情况下得到不同的复杂性)。对于N=10亿，lg(N)约为29,8，因此它接近32，因此接近w= 32。
2. 如果假设现在比较16位值，那么w= 64/16 =4(一个键包含4个16位值)。这是一个相对较小的常数，因此总成本Nw渐近接近N。
3. 作者所指的“字节”是生成密钥的单个片段的大小。因此，如果您对基排序的char数组进行排序，您可能会对“逐字符”进行排序，您的字节将为8位(对于标准字符)。但是如果你用基数排序一些奇怪的元素，这些元素是前人的“合成”元素。16位碎片，你的字节是16位。