arrays - 合并排序变体 n+m，困惑

Question

令 A 为已按升序排序的 n 整数数组。
令 B 为未排序的 m 整数数组。
我们知道 A 中的整数集与 B 中的整数集不相交。描述一种生成数组的算法，其中所有 n + m 整数均已按升序排序。您的算法应在 O(n + m log m) 时间内终止。

我知道这应该类似于合并排序，但是 O(n+mlogm) 中的 n+m 让我失望了。谁能解释一下？

Answer 1

我认为你应该先对 B 数组进行排序:O(mlogm)
之后你有两个排序的数组，你需要合并它们，这将花费:O(n+m)
现在整个过程是 O(mlogm + (n+m) ) 等于 O(mlogm)。