CSP-S 提高级 · CSP 2019 提高级第一轮 第 11 题

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

这题别急着套公式，先想合并过程的本质：两个有序数组合并，每次比较只能把一个小元素‘请’出去。当只剩一个数组没空时，剩下的直接搬过去不用比了，所以最坏就是 2n-1 次。

最容易掉进两个坑：一是死记‘归并排序复杂度 O(n log n)'，把合并阶段的比较次数和总排序复杂度搞混；二是机械数次数，以为两个数组各 n 个元素就要比 2n 次，忘了最后一步是‘无脑归位’。还有人会把‘至少’理解成下界 n，其实题目问的是最坏情况下的下界，也就是最坏情形里不得不做的最少比较数。

归并比较次数的最坏下界分析

这题考什么

这题核心就是归并（Merge）过程的比较次数下界，属于分治算法里最基础的复杂度分析。很多同学看到“归并”就条件反射想归并排序的总复杂度 O(n log n)，或者只记得合并是线性的 O(n)，但具体到“最坏情况下至少比多少次”，需要把合并过程拆开看。