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

Question

考虑一个n数字具有最大k数字的数组(请参阅编辑).从这里考虑基数排序程序:

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基本上是所有的数字的2D名单.但是,只会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 的答案中提到的问题的实现和实现的空间复杂度是O(n+k)。但k不是最长单词（或最长数字）的长度。k是“字母表”的大小：不同数字（数字）或字母（单词）的数量。

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

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

编辑：在此placement实现中， (或tmp)的大小是O(k)（与您的定义相同k），因为k是 log(maxNumber)base 10，并且placementsize 是log(maxNumber)base 256。但我不确定这是一般情况。