求分析
两个序列,长度分别为m、n
求出和序列中第k小的值
我试过一些算法,但是得出的结论是蛮力法算出和序列,然后快排是最快的
如果哪位有更好的算法请指教,如果能给出理论的复杂度分析,以及与蛮力快排的比较,就更好了
[解决办法]
分别用快排的“前半部分”,最后一步将两组快排的合并(交叉插入)。
算法复杂度:mlogm+nlong<(m+n)log(m+n)
发布时间: 2012-03-08 13:30:13 作者: rapoo
求分析
两个序列,长度分别为m、n
求出和序列中第k小的值
我试过一些算法,但是得出的结论是蛮力法算出和序列,然后快排是最快的
如果哪位有更好的算法请指教,如果能给出理论的复杂度分析,以及与蛮力快排的比较,就更好了
[解决办法]
分别用快排的“前半部分”,最后一步将两组快排的合并(交叉插入)。
算法复杂度:mlogm+nlong<(m+n)log(m+n)