当将两个长度为n的有序表A=(a1,a2,.,an)与B=(b1,b2,.,bn),(ai≠bj,1≤i,j≤n)归并为一个有序表C=(c1,c2,...,c2n)时,所需进行的元素比较次数最少可达n,最多可达2n-1.1)假设有序表C=(2,4,5,6,7,9),试举

Question

当将两个长度为 n 的有序表 A=(a1,a2,.,an)与 B=(b1,b2,.,bn),(ai≠bj,1 ≤i,j≤n)归并为一个有序表 C=(c1,c2,...,c2n)时,所需进行的元素比较次数 最少可达 n,最多可达 2n-1.
1)假设有序表 C=(2,4,5,6,7,9),试举出两组 A 与 B 的例子,使它们在 归并过程中进行的元素比较次数分别达到最少和最多; 2)写出一般情况下,使归并所需进行的元素比较次数分别达到最少和最 多时,A 与 B 中的元素应满足的条件.

Answer 1

1)A=(2,4,5) B=(6,7,9) 比较次数最少
A=(2,5,7) B=(4,6,9) 比较次数最多
2）最少就是A、B两个有序表的元素一个是有序表的前n个元素,一个是有序表的后n个元素,即A的最后一个元素比B的第一个元素大或者小
最多情况就是A、B的最后一个元素为有序表的最后两个元素