合并两个排序数组的最坏情况下的比较次数？
Number of Comparison in Worst Case of Merging Two Sorted Array?
给定两个排序数组 A, B，大小为 n 和 m。我正在寻找合并这两个数组的最差比较次数。
1) n+m-1
2) 最大值(n,m)
3)min (m,n)
4) 百万
我知道这不是一个好问题，因为没有提到合并算法，但我认为，正常的合并排序算法 - 合并步骤通常应用 n + m -1 比较，其中一个列表的大小为 n 并且另一个列表的大小为 m。使用此算法是组合两个排序列表的最简单方法。任何专家都可以帮助我，我选择（1）是否正确？
这可以很容易地从documentation中找到：
Complexity
At most std::distance(first1, last1) + std::distance(first2, last2) - 1 comparisons.
所以它是第一名。 （是的，它假设标准委员会正确地理解了复杂性，但这不是一个延伸。）
选项 4 显然是错误的，因为 n + m - 1 的增长速度比 n*m 慢，所以我们已经有了更好的估计。
对于这个反例，选项 3 是错误的：
[4], [1, 2, 6, 7]
至少需要两次比较。选项2反例：
[1,6], [2,5]
需要 3 次比较：
1 < 2?, 6 < 2?, 6 < 5?
假设m < n，至少m次比较，最多n+m-1次比较（最坏情况）。所以假设最小列表的所有元素都在前，则最小比较次数为min(n,m)。假设最简单的意思是最好的情况，那么答案 3 就是正确答案。对于最坏的情况，答案 1 是正确的。
给定两个排序数组 A, B，大小为 n 和 m。我正在寻找合并这两个数组的最差比较次数。
1) n+m-1
2) 最大值(n,m)
3)min (m,n)
4) 百万
我知道这不是一个好问题，因为没有提到合并算法，但我认为，正常的合并排序算法 - 合并步骤通常应用 n + m -1 比较，其中一个列表的大小为 n 并且另一个列表的大小为 m。使用此算法是组合两个排序列表的最简单方法。任何专家都可以帮助我，我选择（1）是否正确？
这可以很容易地从documentation中找到：
Complexity
At most std::distance(first1, last1) + std::distance(first2, last2) - 1 comparisons.
所以它是第一名。 （是的，它假设标准委员会正确地理解了复杂性，但这不是一个延伸。）
选项 4 显然是错误的，因为 n + m - 1 的增长速度比 n*m 慢，所以我们已经有了更好的估计。
对于这个反例，选项 3 是错误的：
[4], [1, 2, 6, 7]
至少需要两次比较。选项2反例：
[1,6], [2,5]
需要 3 次比较：
1 < 2?, 6 < 2?, 6 < 5?
假设m < n，至少m次比较，最多n+m-1次比较（最坏情况）。所以假设最小列表的所有元素都在前，则最小比较次数为min(n,m)。假设最简单的意思是最好的情况，那么答案 3 就是正确答案。对于最坏的情况，答案 1 是正确的。