珍爱生命，远离政治。我们继续讨论算法。
2008/04/01补充：此算法有重大缺陷。详情请见留言部分。
一年前，我们讨论过一个算法问题，perfect shuffle，据称是个微软面试题：
输入
，如何用
的时间，
的空间，将这个序列顺序改为
。
那一次讨论我们翻出了问题的来源，一篇长达12页的论文Computing the Cycles in the Perfect Shuffle Permutation，算法那是非常的复杂，我估计贴出来都没几个人仔细看。
这一次，Xie Xie（没错，又是他 
）翻出了Art of Computer Programming, Volume 3上的一个难度为40分的Merge Sort习题：
已知数列
，设计算法使得在线性时间，常数空间实现归并，也就是将原数组排序。
而Perfect Shuffle问题是可以规约到这个Merge Sort问题的：
mergeSort(x[1...2n]); // if this function solve Merge Sort problem perfectShuffle(x[1...2n]): // then this solve Perfect Shuffle problem m <- max(x[1...2n])+1; x[i] <- x[i]+(2i-1)m, x[i+n] <- x[i+n] + 2im mergeSort(x[1...2n]) x[i] <- x[i]%m
原来我还不相信这个问题会是一个面试题。现在我信了。因为那个归并排序的算法还是有些牛人会知道的。
很好很强大。
另注：从2006年4月1号愚人节开始，阅微堂成立两周年了。
过去一年，阅微堂共发表了201篇文章，其中包括Liu Tao先生的19篇文章，sog white的17篇文章，以及一些授权转载的网友原创作品。共3389条留言。
感谢大家的关注和对阅微堂的支持。
留言
- roy_hu said: 虽然如此，复杂程度并没有降低啊。还是一个论文级别的题目。最早由Kronrod解决，题为“An Optimal Ordering Algorithm Without a Field of Operation”，原文似已不可考。
- dstyler said: 阅微堂,见微知著，哈哈
- haha said: 你的规约改写了x数组的值。 如果可以改写的话，O(1)空间O(N)时间的算法是显然的。
- zhiqiang said: 我提到的那篇论文的方法非常复杂，面试的时候不可能想出来。而且实际空间复杂度是$$O(\log n\log\log n)$$。
- Think said: 你说的办法是否是这样： 每个元素进行了改写，意味着它带了一附加的信息即下标。 然后再用生成元的办法。 如果某位置的元素所携带下标是它应该放置的位置，如2位置已经放的是b_1了，则不动；反之利用这个元素一直push它后面乘2加1的元素直到返回此点。 这就是加了一个bool标记。 请问haha同学是？
- Think said: 那个人好像是个俄罗斯人 M A Kronrod, "An Optimal Ordering Algorithm without a Field of Operation," Dok Akad Nauk SSSR 186 (1969), 1256-1258 杂志是俄文的:-)
- zhiqiang said: 对的. 经过改写后, 增加了附加信息, 已经相当于使用了更多的空间. 所以文章中写的规约的算法不能算一个解法. 这次无意中弄出了一个愚人节笑话, :han
© zhiqiang for 阅微堂, 2008. | 链接 | 7 条评论