Sid*_*Sid 16 arrays sorting algorithm mergesort space-complexity
我遇到了以下问题.
给定n个元素的数组和整数k,其中k < n.元素{ a 0 ... a k }和{ a k +1 ... a n }已经排序.给出一个算法在O(n)时间和O(1)空间中排序.
在我看来,它不能在O(n)时间和O(1)空间中完成.问题实际上似乎是询问如何进行mergesort的合并步骤,而不是就地.如果有可能,那么不会以这种方式实现mergesort吗？我无法说服自己,但需要一些意见.
这似乎表明可以在O(lg ^ 2 n)空间中进行.我看不出如何证明在恒定空间中合并是不可能的,但我也看不出怎么做.
编辑:追逐参考文献,Knuth Vol 3 - 练习5.5.3说"一个相当复杂的L. Trabb-Pardo算法为这个问题提供了最好的答案:可以在O(n)时间内稳定合并并稳定在O(n lg n)时间内进行排序,仅使用O(lg n)位的辅助存储器来存储固定数量的索引变量.
更多我没有读过的参考文献.谢谢你有趣的问题.
进一步编辑:本文声称Huang和Langston的文章有一个算法,它在时间O(m + n)中合并了两个大小为m和n的列表,所以你的问题的答案似乎是肯定的.不幸的是我无法访问该文章,因此我必须信任二手信息.我不确定如何与Knuth关于Trabb-Pardo算法最优的声明进行调和.如果我的生活依赖于它,我会和Knuth一起去.
我现在看到这个曾被要求为和早期堆栈溢出问题一个数十倍.我没有心脏将它标记为重复.
黄B.-C. 和Langston MA,实用就地合并,Comm.ACM 31(1988)348-352
| 归档时间： |
|
| 查看次数： |
2074 次 |
| 最近记录： |