算法第二章实验报告

实践题目名称

7-3 两个有序序列的中位数

问题描述：

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,A**N−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。

算法描述

本题采用了分治中的二分法。 主要体现在寻找第n个值时，先二分取2个数组的中位数。(另数组为a[n],b[n])

若a的中位数比b的大，由于数组为非降序排列，可知，第n个数在a[0]-a[mid]和b[mid]-b[n]之间。反之，则在b[0]-b[mid]和a[mid]-a[n]之间。如此循环取剩余数组的中位数直至left==right退出循环。此时a[right]和b[right]小的即为解。

do while(right1 != left1 || right2 != left2)
{
    if(a[mid1] == b[mid2]) return a[mid1];
    if(a[mid1] < b[mid2])
    {
        left1 = mid1 + (right1 - left1+1)%2;
        right2 = mid2;
    }
    else
    {
        right1 = mid1;
        left2 = left2 + (right2 - left2+1)%2;
    }
        
}

算法时间复杂度及空间复杂度分析

本题只需查找，无需排序且数组长度相等。

时间复杂度即为 O(logn)

空间复杂度 O(n)

心得体会

本题在对分比较时，相对难以找到其对分后，左右边界移动规律 以及 循环退出条件。 可以在纸上进行一定规模的数据演练，从而查找规律。

分治的个人体会和思考

分治是对去年学习的递归以及排序的加深应用，从而实现高效排序。

而分治在一些特殊方面，没有亮眼的表现，在使用前可进行算法时间复杂度的比较，并对递归关系公式进行优化以谋求缩减时间。