※ 引述《DJWS (...)》之铭言： : FRAXIS 这是你的文章吗？ : http://algnotes.wordpress.com/2014/10/09/ 哈，被发现了。 : 看完这个我就想通了 : 行列已排序的阵列，可以用阶梯状移动的方法找rank（做partition），O(n) : 只有行排序的阵列，可以用 n 次 binary search 找 rank (做partition)，O(n log n) : 所以是 O(log n) 回合没错 : 行列已排序是 O(n logn) : 只有行排序是 O(n logn logn) 其实我之前还想到一个变形，就是给定常数个排序阵列找第 k 位。 如果套用行排序的方法，会需要O(lg^2 n)。 但是我们知道两个阵列找中位数只需要O(lg n)的时间。 不过如果用我之前说的方法，找中位数就只需要O(lg n)的时间了。 : 最後我还是想问，学术界有人做过这个题目吗？ : 还是说文章中的 reference paper 就是这个方法？ : 我想整理到演算法笔记上面 那篇paper是讲行列排序时O(n)的方法。 只有行排序的方法，我也有找到一些资料。 http://algnotes.wordpress.com/2010/05/30/finding-median-in-3-arrays/ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 129.170.195.148 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1413546030.A.DC3.html