题7

题7

题目

Q:将两个各有 个元素的有序表合并成一个有序表,最少比较次数 ( ),最多比较次数 ( )
A. B. C. D.

分析

A:和题6对比起来看这个公式，归并次数和比较次数的区别
一共2N个元素，两路归并，排序m趟，满足，所以m =

解

A、B
注意, 当一个表中的最小元素比另一个表中的最大元素还大时, 比较的次数是最少的, 仅比较 次;
而当两个表中的元素依次间隔地比较时,即 时,比较的次数是最多的,为 次。
建议读者对此举一反三: 若将本题中的两个有序表的长度分别设为 和 ,则最多 (或最少) 的比较次数是多少? 时间复杂度又是多少?