fre*_*low 13 algorithm complexity-theory terminology quicksort space-complexity
Quicksort通常被描述为原位(就地)算法,尽管它需要O(log n)堆栈空间.所以,做原地意味着"需要小于O(n)的额外空间",还是栈空间一般不能算作空间复杂度(但为什么会这样呢？),或者是快速排序实际上不是原地算法？
jas*_*son 14
Quicksort实际上不是原位算法吗？
它的标准实施不是 原位的.这是一个非常普遍的误解,但你正确地注意到由于堆栈空间消耗,这个概念是错误的.
我说它的"标准实现"是因为人们已经修改了算法以使其成为O(1)空间算法.这是一个例子:没有堆栈的Quicksort.
当然,与经典的时空权衡相一致,此类快速排序版本的性能不如标准实现.
维基百科提供以下定义:
在计算机科学中,就地算法(或原位拉丁语)是一种算法,该算法使用具有小的,恒定量的额外存储空间的数据结构来转换输入.
根据这个定义,典型的基于堆栈的快速排序显然不是原位算法.
事实上,维基百科的文章明确地讨论了这个问题:
算法有时是非正式调用的,只要它用输出覆盖其输入即可.实际上,这还不够(如快速通道的情况所示),也不是必要的; 输出空间可以是常数,或者甚至可以不计数,例如,如果输出是流.
和
Quicksort通常被描述为就地算法,但事实并非如此.大多数实现需要O(log n)空间来支持其除法和征服递归.
然而,正如@Jason在其出色的答案中所指出的,似乎存在快速排序的变体,其仅需要O(1)额外空间.任何此类算法都将在原地考虑.