为什么基数排序的复杂度为 space 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 个值。为什么 space 复杂度是 O(k + n) 而不是 O(n)？如果我错了请纠正我，即使我们考虑用于在特定位置提取数字的 space，它也仅使用 1 个（常量）内存 space?

编辑：我想解释一下我对k的理解。假设我给出 [12, 13, 65, 32, 789, 1, 3] 的输入，link 中给出的算法将经过 4 遍（函数内的第一个 while 循环）。这里k = 4，即最大编号。数组中任意元素的位数 + 1。因此 k 为否。通行证。这与此算法的时间复杂度中涉及的 k 相同：O(kn) 这是有道理的。我无法理解它如何在 space 复杂性中发挥作用：O(k + n)。

Answer 1

基数排序的 space 复杂性与其用于对每个基数进行排序的排序有关。最好的情况是计数排序。

这里是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的辅助数组。

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

Answer 2

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

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

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

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

Answer 3

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

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

表示总共space使用的是总位数*（n+基数）。如果总位数不变。 space 复杂度变为 O(n+base)。

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

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

Why does radix sort have a space complexity of O(k + n)?

python

algorithm

sorting

space-complexity

radix-sort