将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是()

Question

将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是()为什么是n

Answer 1

最少比较n次，最多比较2n-1次。可以很容易得到每次比较必定会归并一个元素。若其中一个有序表的最大元素都小于另一个有序表的最小值，那么只需要比较n次，另一个表直接放入即可。同理最多比较2n-1次。
举例：
1 2 3 4 5
6 7 8 9 10 只需要比较5次
1 3 5 7 9
2 4 6 8 10 需要比较9次