是否存在具有线性时间复杂度和O(1)辅助空间复杂度的排序算法? [英] Is there a sorting algorithm with linear time complexity and O(1) auxiliary space complexity?
问题描述
如果仅对整数排序，则可以使用具有 O(k)空间复杂度的计数排序的原位变体，它独立于变量 n .换句话说，当我们将 k 视为常量时，空间复杂度为 O(1).
或者，我们可以在空间为阶段(由于递归).甚至更少的阶段使用计数排序来确定n路分区的存储桶边界.这些解决方案的时间复杂度为 O(lg k)的二进制分区的lg k O(lg k * n)，当仅用变量 n 表示时，其复杂度为 O(n)(当 k 被认为是常量时).
当将 k 视为常量时，获得 O(n)步复杂度和 O(1)空间复杂度的另一种可能方法是使用OP中自己的答案或宾果排序，它具有步骤复杂性O(vn)，其中 v< = k 是输入中唯一值的数量，以及空间复杂度 O(1).
请注意，这些排序解决方案都不是稳定的，如果我们对不仅仅是整数(某些带有整数键的任意对象)进行排序，这将很重要.
此纸
常规计数排序(来自Wikipedia)
count = k + 1个零的数组对于输入中的xcount [key(x)] + = 1总计= 0因为我在0,1，... kcount [i]，总数=总数，count [i] +总数输出=与输入长度相同的数组对于输入中的x输出[计数[键(x)]] = xcount [key(x)] + = 1返回输出 假定输入由某些对象组成，这些对象可以由范围为 0 到 k-1 的整数键标识.它使用 O(n + k)多余的空间.
普通的整数变体
此变体要求输入为纯整数，而不是带有整数键的任意对象.它只是从count数组重构输入数组.
count = k个零的数组对于输入中的x计数[x] + = 1我= 0对于x in 0，1，... k-1 do对于1，2，j中的j ... count [x]做输入[i]，i = x，i + 1返回输入 它使用 O(k)多余的空间.
具有整数键的任意对象的完整原位变体
与常规变量类似，此变量接受任意对象.它使用交换将对象放置在适当的位置.在前两个循环中计算完 count 数组后，它保持不变，并使用另一个名为 done 的数组来跟踪已经放置了多少个具有给定键的对象在正确的位置.
count = k + 1个零的数组对于输入中的xcount [key(x)] + = 1总计= 0因为我在0,1，... kcount [i]，总数=总数，count [i] +总数完成= k个零的数组对于i in 0，1，... k-1 do当前=计数[i] +完成[i]完成时[i]<count [i + 1]-count [i]做x =输入[当前]目的地=计数[键(x)] +完成[键(x)]如果目的地=当前，则当前+ = 1别的swap(输入[当前]，输入[目的地])完成[key(x)] + = 1返回输入 此变量不稳定，因此不能用作基数排序的子例程.它使用 O(2k)= O(k)多余的空间.
Is there a sorting algorithm with linear time complexity and O(1) auxiliary space complexity to sort a list of positive integers? I know that radix sort and counting sort have linear time complexity (O(kn) and O(n+k) respectively if we take k as constant), but both of them have O(n+k) auxiliary space complexity. Is it even possible for a sort to have both of these properties? An example of such a sort would be appreciated.
If we are sorting only integers, we can use the in-situ variant of counting sort which has O(k) space complexity, which is independent from the variable n. In other words when we treat k as constant, the space complexity is O(1).
Alternatively, we can use in place radix sort with lg k phases of binary partition with O(lg k) space complexity (due to recursion). Or even less phases with the use of counting sort to determine the buckets boundaries for the n-way partition. These solutions sport time complexity of O(lg k * n), which when expressed only in terms of the variable n is O(n) (when k is considered constant).
Another possible approach to obtain O(n) step complexity and O(1) space complexity, when k is considered constant, is to use something which can be called subtraction sort, as described by the OP in their own answer, or elsewhere. It has step complexity O(sum(input)) which is better than O(kn) (and for certain specific inputs it is even better than binary-radix sort's O(lg k * n), e.g. for all inputs of the form [k, 0, 0, ... 0]) and space complexity O(1).
Yet another solution is to use bingo sort which has step complexity O(vn) where v <= k is the number of unique values in the input, and space complexity O(1).
Note that neither of these sorting solutions are stable, which matters if we sort something more than just integers (some arbitrary objects with integer keys).
There is also a cutting edge stable partition algorithm described in this paper with O(1) space complexity. Combining it with radix sort, one may construct a stable linear sort algorithm with constant space - O(lg k * n) step complexity and O(1) space complexity.
EDIT:
As per the request from the comment, I've tried to find a source for the "in-situ" variant of counting sort, but haven't found anything of good quality I could link to (it's really strange that there is no easily available description for such a basic algorithm). Therefore, I'm posting the algorithm here:
The regular counting sort (from Wikipedia)
count = array of k+1 zeros
for x in input do
count[key(x)] += 1
total = 0
for i in 0, 1, ... k do
count[i], total = total, count[i] + total
output = array of the same length as input
for x in input do
output[count[key(x)]] = x
count[key(x)] += 1
return output
It assumes that the input consists of some objects which can be identified by an integer key in the range 0 to k - 1. It uses O(n + k) extra space.
The trivial in-situ variant for integers
This variant requires the input to be pure integers, not arbitrary objects with integer keys. It simply reconstructs the input array from the count array.
count = array of k zeros
for x in input do
count[x] += 1
i = 0
for x in 0, 1, ... k - 1 do
for j in 1, 2, ... count[x] do
input[i], i = x, i + 1
return input
It uses O(k) extra space.
The complete in-situ variant for arbitrary objects with integer keys
This variant accepts arbitrary objects similarly to the regular variant. It uses swaps to place objects in appropriate places. After computing the count array in the two first loops it leaves it immutable, and uses another array called done to keep track of how many objects with a given key have been already placed in the right position.
count = array of k+1 zeros
for x in input do
count[key(x)] += 1
total = 0
for i in 0, 1, ... k do
count[i], total = total, count[i] + total
done = array of k zeros
for i in 0, 1, ... k - 1 do
current = count[i] + done[i]
while done[i] < count[i + 1] - count[i] do
x = input[current]
destination = count[key(x)] + done[key(x)]
if destination = current then
current += 1
else
swap(input[current], input[destination])
done[key(x)] += 1
return input
This variant is not stable, so it cannot be used as a subroutine in radix sort. It uses O(2k) = O(k) extra space.
这篇关于是否存在具有线性时间复杂度和O(1)辅助空间复杂度的排序算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
