任何以元素比较作为基本运算的归并算法,在最坏情况下至少要做多少次比较

2021年9月6日 | 分类: 【编程】

【题目】

设A和B是两个长为n的有序数组,现在需要将A和B合并成一个排好序的数组,请问任何以元素比较作为基本运算的归并算法,在最坏情况下至少要做多少次比较?( )。

A. n^2
B. n log n
C. 2n
D. 2n-1

【解析(1)】

可以试着枚举。

当 n=1 时,一共2个数字,只需要比较1次。答案可能是 A/D 。
当 n=2 时,

答案选择:D

【解析(2)】

只要比较能进行到两个序列的最后一个数即可。

每次比较排好一个数,最后一次比较直接排好两个数。

所以最多的比较次数为:2n-1

答案选择:D