Ake*_*nan 30 algorithm computer-science quicksort in-place space-efficiency
所以Quicksort的空间效率是O(log(n)).这是维护调用堆栈所需的空间.
现在,根据Quicksort上的维基百科页面,这可以作为就地算法,因为算法只是交换输入数据结构中的元素.
然而,根据这个页面,空间效率O(log n)使Quicksort不合格,因为它的空间效率大于O(1).根据该定义,任何空间效率大于O(1)的算法都不是就地的.所以我认为这意味着根据定义,所有递归算法都没有到位？
显然,这里有两种不同的就地定义.维基百科并不总是一个完全可靠的来源,所以我咨询了我的一位教授.
我的教授同意第二个定义.他说Quicksort不到位.即使数据保留在输入数组中,堆栈所需的额外空间也会使其失去资格.我的教授写了一本关于算法的畅销书,所以我非常尊重他的观点,但这个答案对我来说似乎不正确.
我认为就地的属性非常直观.数据保持不变.它不会从它的原始数据结构中移动.对我来说,这个定义更有用,因为它意味着您可以使用指针执行算法,而不是要求您复制数据.这似乎是算法的一个有价值的属性,并且名副其实"就地".
C.B*_*.B. 19
来自麻省理工学院出版社的算法简介将 QuickSort定义为就地 - 它在阵列中对元素进行排序,在任何给定时间内,它们在阵列外最多只有一定数量的元素.
在一天结束时,人们将总是有不同的意见(自上而下的Memoization被认为是动态编程？不是一些"经典"的人),一边是你最信任的人.我相信麻省理工学院出版社的编辑和作者(以及我的教授,他将其作为就地资格).
通常情况下,QuickSort的问题不在于它不是就地排序,而是它不稳定 - 卫星数据不能保持有序.
编辑
Kuroi的观点强调了我认为非常重要的一部分论点.
许多人认为它需要O(log(n))额外的内存用于递归调用,并且数据以堆栈上的索引的形式泄露,但是对于非常大的N(log(1,000,000,000)= ~30,这可以忽略不计并且它忽略了这样的事实:当大小(数据)>>大小(索引)时,通常在堆上移动数据需要更长时间.
数据的索引本身不是元素 - 因此数据的元素不会存储在数组之外,而是存储在数组中(在每次调用中).
小智 7
严格来说,Quicksort的空间效率为O(n),因为退化情况需要在数组的每个元素的堆栈上有一个索引.虽然平均而言它将是O(log(n)).鉴于我认为没有任何方法可以将其称为"就地"算法,除非您使用"原位"的简并定义,这意味着原始数据不会存储在原始数组边界之外(不包括复制/交换操作).
这种"就地"的定义将是退化的,因为你可以采取任何"不合适"的算法,并通过让它所有的额外数据存储使用指向原始数组的指针来满足这种"就地"要求.然后,当找到答案时,您可以使用指针数据"就地"重新排序原始数组.