位排序的 Space 复杂度是多少？
What is the Space Complexity of Bit Sorting?
位排序的Space复杂度是多少？根据其最佳和平均情况，它是 O(n)。我想知道它的 space 复杂性是多少
来源标题：位排序：排序新技术
IEEE 研究只关注时间复杂度。
谢谢！
它是 O(n)，因为您没有在某个变量的函数中创建任何新元素。只需检查它的位表示和交换位置。所以基本上，在这些步骤中：
Step 1: convert all elements into binary form but converted elements are in same BIT
sequence form.
Step 2: find elements whose first leftmost bit is 1
Step 3: repeat step 2 to all selected elements until get single BIT sequence number
Step 4: swap selected BIT sequence with last element of an array
Step 5: repeat step2, step3 and step4 until all elements are sorted
Step 6: convert sorted BIT sequence elements into decimal number
理论上，当您可以直接访问给定元素的位值时，您没有任何新元素。
但是，如果您确实在其位表示中创建给定元素的深层副本，然后再次转换回元素，它仍然是 O(n)（只是 3*n）。现在交换元素的深拷贝，你仍然需要最多 n 个新内存 spaces（n 是当你在交换时总是在内存中使用新的 space ）。使用深拷贝交换时的最佳情况是你只需要一个内存 space。指针交换也是如此。所以总的来说，它 O(n).
位排序的Space复杂度是多少？根据其最佳和平均情况，它是 O(n)。我想知道它的 space 复杂性是多少
来源标题：位排序：排序新技术
IEEE 研究只关注时间复杂度。
谢谢！
它是 O(n)，因为您没有在某个变量的函数中创建任何新元素。只需检查它的位表示和交换位置。所以基本上，在这些步骤中：
Step 1: convert all elements into binary form but converted elements are in same BIT
sequence form.
Step 2: find elements whose first leftmost bit is 1
Step 3: repeat step 2 to all selected elements until get single BIT sequence number
Step 4: swap selected BIT sequence with last element of an array
Step 5: repeat step2, step3 and step4 until all elements are sorted
Step 6: convert sorted BIT sequence elements into decimal number
理论上，当您可以直接访问给定元素的位值时，您没有任何新元素。
但是，如果您确实在其位表示中创建给定元素的深层副本，然后再次转换回元素，它仍然是 O(n)（只是 3*n）。现在交换元素的深拷贝，你仍然需要最多 n 个新内存 spaces（n 是当你在交换时总是在内存中使用新的 space ）。使用深拷贝交换时的最佳情况是你只需要一个内存 space。指针交换也是如此。所以总的来说，它 O(n).