为什么基数排序的空间复杂度为O（k + n）？

Question

考虑具有n数字的数组，其具有最大k数字（参见编辑）。考虑here的基数排序程序：

def radixsort( aList ):
  RADIX = 10
  maxLength = False
  tmp, placement = -1, 1

  while not maxLength:
    maxLength = True
    # declare and initialize buckets
    buckets = [list() for _ in range( RADIX )]

    # split aList between lists
    for  i in aList:
      tmp = i / placement
      buckets[tmp % RADIX].append( i )
      if maxLength and tmp > 0:
        maxLength = False

    # empty lists into aList array
    a = 0
    for b in range( RADIX ):
      buck = buckets[b]
      for i in buck:
        aList[a] = i
        a += 1

    # move to next digit
    placement *= RADIX

buckets基本上是所有数字的第二个列表。但是，只会添加n值。为什么空间复杂度是O（k + n）而不是O（n）？如果我错了，请纠正我，即使我们考虑用于在特定位置提取数字的空间，它只使用1（常量）内存空间？

编辑：我想解释一下我对k的理解。假设我给出了[12, 13, 65, 32, 789, 1, 3]的输入，链接中给出的算法将经历4次传递（函数内的第一个while循环）。这里k = 4，即最大数量。数组中任何元素的数字+ 1.因此k为否。通行证这与参与该算法的时间复杂度的k相同：O(kn)这是有道理的。我无法理解它在空间复杂性中的作用：O(k + n)。

Answer 1

Radix sort的空间复杂度与它用于对每个基数进行排序的排序绑定。在最好的情况下，这是排序。

以下是CLRS提供的用于计数排序的伪代码：

Counting-sort(A,B,k)
  let C[0..k] be a new array
  for i = 0 to k
      C[i] = o
  for j = 1 to A.length
      C[A[j]] = C[A[j]] + 1
  for i = 1 to k
      C[i] = C[i] + C[i-1]
  for j = A.length down to 1
      B[C[A[j]]] = A[j]
      C[A[j]] = C[A[j]] - 1 

如您所见，计数排序会创建多个数组，一个基于K的大小，另一个基于N的大小.B是输出数组，大小为n。 C是大小为k的辅助数组。

因为基数排序使用计数排序，计算排序的空间复杂度是基数排序的空间复杂度的下限。

Answer 2

我认为存在术语问题。 Jayson Boubin's answer中提到的问题实施和实施的空间复杂性是O(n+k)。但k不是最长词（或最长的数字）的长度。 k是'alphabet'的大小：不同数字（数字）或字母（单词）的数量。

buckets = [list() for _ in range( RADIX )]

此代码使用RADIX元素创建一个数组。在这个特定的实现中，RADIX是一个常量（并且空间复杂度是O（n）），但一般来说，它是一个变量。 RADIX是一个k，不同数字的数字（字母表中的字母）。而且这个k不依赖于n，并且在某些情况下可能比n更大，因此空间复杂度通常为O（n + k）。

编辑：在this实现placement（或tmp）的大小是O(k)（与您的定义k），因为k是log(maxNumber)基地10，而placement大小是log(maxNumber)基地256。但我不确定这是一般情况。

Answer 3

基数排序对数据集中每个数字位使用计数排序。计数排序具有O（n + k）的空间复杂度，其中k是数据集中的最大数字。

十进制数字的范围从0到9，所以如果我们使用基数排序（在基数排序中使用的计数排序）对4个十进制数字（11,22,88,99）进行排序，对于每个数字，它将创建大小为b = 10的数组，其中b是基地。

这意味着使用的总空间将是总数*（n +基数）。如果总数是常数。空间复杂度变为O（n + base）。

因此，Radix Sort的空间复杂度为O（n + b）。