Ste*_*314 36
就地算法的想法并不是排序所独有的,但排序可能是最重要的情况,或者至少是最知名的.这个想法是关于空间效率 - 使用最少量的RAM,硬盘或其他可以逃脱的存储.这可以追溯到几十年前,当硬件更加有限时.
我们的想法是通过连续转换数据直到产生输出,在包含输入的同一存储空间中产生输出.这样就无需使用两倍的存储空间 - 一个输入区域和一个大小相等的输出区域.
排序是一个相当明显的情况,因为排序可以通过重复交换项目来完成 - 排序只重新排列项目.交换不是唯一的方法 - 例如,插入排序使用稍微不同的方法,相当于进行一系列交换,但速度更快.
另一个例子是矩阵换位 - 再次,这可以通过交换项目来实现.添加两个非常大的数字也可以就地完成(结果替换其中一个输入)从最低有效数字开始并向前传播.
当你想到堆叠的穿孔卡片时,重新排序,重新安排"就地"的优势变得更加明显- 最好避免复制穿孔卡片来对它们进行分类.
一些排序算法允许这种就地操作,而不是.
但是,所有算法都需要一些额外的存储空间来处理变量 如果目标只是通过连续修改输入来生成输出,那么通过保留大量内存来定义算法是相当容易的,使用它来生成一些辅助数据结构,然后使用它来指导这些修改.你仍然通过"输入"转换输入来产生输出,但是你正在击败练习的全部内容 - 你没有节省空间.
因此,就地定义的正常定义要求您达到一定的空间效率标准.使用与输入成比例的额外空间(即O(n)额外空间)并且仍然"就地"调用算法是绝对不可接受的.
关于就地算法的维基百科页面目前声称就地算法只能使用恒定量--O(1) - 额外空间.
在计算机科学中,就地算法(或原位拉丁语)是一种算法,该算法使用具有小的,恒定量的额外存储空间的数据结构来转换输入.
In Computational Complexity部分中指定了一些技术细节,但结论仍然是例如Quicksort需要O(log n)空间(true),因此不是就地(我认为是假的).
O(log n)远小于O(n) - 例如,16,777,216的基数2对数是24.
Quicksort和heapsort通常都被认为是就地的,而heapsort可以用O(1)额外的空间来实现(我之前错了).Mergesort更难以就地实现,但是不合适的版本对缓存非常友好 - 我怀疑实际的实现接受O(n)空间开销 - RAM很便宜但内存带宽是一个主要的瓶颈,所以用于缓存效率和速度的交易记忆通常是一个很好的交易.
[ 编辑当我写上面的内容时,我假设我正在考虑对数组进行就地合并排序.链表的就地合并排序非常简单.关键的区别在于合并算法 - 在没有复制或重新分配的情况下进行两个链接列表的合并很容易,对两个较大阵列的子阵列(没有O(n)辅助存储器)做同样的事情AFAIK不是]
Quicksort也具有缓存效率,即使是就地,但可以通过吸引最坏情况的行为来取消作为就地算法的资格.存在退化情况(在非随机版本中,通常在输入已经排序时),其中运行时间是O(n ^ 2)而不是预期的O(n log n).在这种情况下,额外的空间要求也增加到O(n).但是,对于大型数据集和一些基本预防措施(主要是随机枢轴选择),这种最坏情况的行为变得非常不可能.
我个人认为,O(log n)额外空间对于就地算法是可以接受的 - 它不会作弊,因为它不会破坏原始的就地工作点.
但是,我的意见当然只是我的意见.
一个额外的注意事项 - 有时,人们会因为输入和输出都有一个参数而就地调用函数.它不一定表示函数是空间有效的,结果是通过转换输入产生的,或者甚至参数仍然引用相同的存储区域.这种用法是不正确的(或者说是原始主义者会声称的),尽管它是最常见的,最好是要注意但不要对此感到压力.