合并两个排序数组的最佳情况是什么？
what would be the best case scenario of merging two sorted array?
我知道合并两个排序数组需要 O(m+n) 时间，其中 m 和 n 是两个数组的长度。
最大比较次数为(m+n-1)。
但是我的一位学校老师说只有平均和最坏的情况需要 O(m+n) 时间。最好的情况需要 O(1) 时间。
在这里我无法理解最好的情况如何花费 O(1)。
请提及最佳情况以及在回答时如何花费 O(1) 时间。
让我们首先考虑确定两个已排序集合中元素的正确顺序的最佳情况复杂性（无需担心它们的存储方式）。
如果第一组中的最后一个元素小于第二组中的第一个元素，则只需进行一次比较即可确定正确的顺序。第二组只需要 "tacked on" 到第一组结束。 （大多数实现会从两个集合的前面开始，但您可以将其写为排序开始时的 "special case" 检查。）
由于这种情况只进行一次比较，无论数组中的元素数量如何，在最佳情况下确定正确的顺序是 O(1)。
现在，回到元素存储在数组中的问题...
在许多语言中，数组一旦创建就无法调整大小 - 合并两个数组需要分配第三个数组，该数组的大小足以包含所有元素。如果是这种情况，你保证至少执行 m + n 操作，因为你必须将所有元素复制到一个新数组中。
即使可以调整第一个数组的大小以容纳其他元素，所有这些元素仍然必须从第二个数组复制到第一个数组 - 这仍然是 n 操作。
因此，虽然确定正确的顺序可以通过恒定数量的比较来完成，但移动元素的工作量在最好的情况下仍然会产生 O(n)。
我知道合并两个排序数组需要 O(m+n) 时间，其中 m 和 n 是两个数组的长度。
最大比较次数为(m+n-1)。
但是我的一位学校老师说只有平均和最坏的情况需要 O(m+n) 时间。最好的情况需要 O(1) 时间。
在这里我无法理解最好的情况如何花费 O(1)。 请提及最佳情况以及在回答时如何花费 O(1) 时间。
让我们首先考虑确定两个已排序集合中元素的正确顺序的最佳情况复杂性（无需担心它们的存储方式）。
如果第一组中的最后一个元素小于第二组中的第一个元素，则只需进行一次比较即可确定正确的顺序。第二组只需要 "tacked on" 到第一组结束。 （大多数实现会从两个集合的前面开始，但您可以将其写为排序开始时的 "special case" 检查。）
由于这种情况只进行一次比较，无论数组中的元素数量如何，在最佳情况下确定正确的顺序是 O(1)。
现在，回到元素存储在数组中的问题...
在许多语言中，数组一旦创建就无法调整大小 - 合并两个数组需要分配第三个数组，该数组的大小足以包含所有元素。如果是这种情况，你保证至少执行 m + n 操作，因为你必须将所有元素复制到一个新数组中。
即使可以调整第一个数组的大小以容纳其他元素，所有这些元素仍然必须从第二个数组复制到第一个数组 - 这仍然是 n 操作。
因此，虽然确定正确的顺序可以通过恒定数量的比较来完成，但移动元素的工作量在最好的情况下仍然会产生 O(n)。