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

Question

考虑一个由n个数字组成的数组，最大有k位数（参见Edit）。考虑来自这里的基数排序程序：

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

桶基本上是一个包含所有数字的二维列表。然而，只有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)。

- skr

Answer 1

基数排序的空间复杂度取决于它用来对每个基数进行排序的排序算法。在最好的情况下，也就是使用计数排序。

以下是 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的辅助数组。

由于基数排序使用计数排序，计数排序的空间复杂度是基数排序空间复杂度的下限。

- Jayson Boubin

---

这完全是错误的。例如，在这里，您可以找到我的原地基数排序实现，其空间复杂度为O(1)。更重要的是，这个答案实际上并没有回答问题。 - hidefromkgb

如果算法采用可变大小的输入，则不能具有O(1)空间复杂度。空间复杂度是衡量算法所需工作存储量的指标。如果一个算法在数组上操作，它需要将该数组作为存储器。原地处理并不意味着O(1)。 - Jayson Boubin

另外，我只是引用了CLRS的话。如果你能证明那些人是错的，那么我觉得你会获得比堆栈溢出声望更多的东西。 - Jayson Boubin

我错了。额外的空间复杂度≠实际空间复杂度。我现在明白你的意思了；+1。 - hidefromkgb

对于接受答案的延迟表示抱歉。直到现在我才完全理解了这个问题。 - skr

Answer 2

我认为这里存在一个术语问题。这个问题的实现和Jayson Boubin的回答中提到的实现的空间复杂度是O(n+k)，但是k并不是最长单词（或最长数字）的长度。k是一个“字母表”的大小：数字中不同数字的数量或单词中不同字母的数量。

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

这段代码创建了一个具有RADIX个元素的数组。在这个特定的实现中，RADIX是一个常量（因此空间复杂度为O(n)），但是通常来说它是一个变量。RADIX是一个k，即不同数字（数字中）或字母（单词中）的数量。而这个k并不依赖于n，在某些情况下甚至可以大于n，因此空间复杂度通常为O(n+k)。 编辑：在这个实现中，placement（或tmp）的大小是O(k)（根据您对k的定义），因为k是以10为底数的maxNumber的对数，而placement的大小是以256为底数的maxNumber的对数。但我不确定这是一个普遍的情况。

- DAle

---

是的。k代表数字的位数。 - skr

我并不认为k与基数或其长度相同。基数始终为10。但是，如果至少有一个三位数，其余数字为2位数或1位数，则k将为3。 - skr

@skr_robo，这就是我所说的。在O(n+k)中，k不是某个数字中最大的位数。 - DAle

如果我们输入这个数组 = [12, 13, 65, 32, 789, 1, 3]，上述算法将运行4次（因为有一个3位数）。现在，时间复杂度是O(kn)，其中k是通过的数量，即4。我的观点是O(k+n)也具有相同的k。我不明白为什么基数在这里起作用？ - skr

我在调用k位最大数字时出错了，它比那个多一个数字。 - skr

Answer 3

基数排序使用计数排序对数据集中的每个数字位进行排序。计数排序的空间复杂度为O(n+k)，其中k是数据集中的最大数字。

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

这意味着所使用的总空间将是总位数 * (n + base)。如果总位数是恒定的，则空间复杂度变为O(n+base)。

因此，基数排序的空间复杂度为O(n+b)。

- Muhammad Amsal