分治法求两列有序数组的中位数的程序

时间:2022-04-01 14:18:21
【文件属性】:

文件名称:分治法求两列有序数组的中位数的程序

文件大小:2KB

文件格式:CPP

更新时间:2022-04-01 14:18:21

教材 C++ 分治

(1)设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数,设计一个算法复杂度为O(logn)的分治算法,找出X和Y中2n个数中的中位数。(中位数:个数为奇数:中间位置上的数;个数为偶数,中间两个数的平均数) 思路:对于两个已排好序的数组,可以寻找两个数组中的中位数,只需要进行n次的比较,时间复杂度可以为O(n),代码如下


网友评论