用大 o 合并和排序 2 个排序数组以寻求澄清。

Question

这是学校作业。我不是在寻找代码帮助，但由于我的老师没有帮助我来到这里。

我被要求在以下两种情况下合并和排序两个已排序的数组：

1. 当两个数组的大小相等时

2. 当两个数组的大小不同时

现在我已经完成了案例 2，它也适用于案例 1：/我只是不明白我如何为案例 1 编写代码或它与案例 2 有何不同。数组长度与问题无关，或者我是没有正确理解。

然后我被要求计算 big(o)。

我不是在这里寻找代码。如果有人有机会真正理解我的老师在问什么，请给我提示来解决它。

Answer 1

学习而不是复制是非常好的。正如您所建议的，情况 1 和 2 之间没有区别，但算法的最坏情况取决于您的解决方案。所以我描述了我的解决方案（没有代码）并给你最坏的情况。您可以在这两种情况下，数组必须以无穷大结束，因此向它们添加无穷大。然后迭代每个数组的所有元素，每次选择较小的元素并放入结果数组中（两个数组的合并）。使用此解决方案，您可以轻松计算最坏情况。我们必须对两个数组迭代一次，如果它们的长度是 n 和 m，那么我们向它们添加无穷大，所以我们最坏和最好的情况是O(m + n)（你做m + n + 2 - 1比较和 -1 因为你不比较两个数组的结尾，我的意思是无穷大）但是为什么添加无穷大会添加数组的末尾？因为为此我们必须制作一个多空间的数组副本？这是一种方式，最坏的情况也是O(m + n)复制数组。但也有另一种解决方案。您可以比较直到到达数组的末尾，然后您必须添加未与结果数组的末尾完全比较的数组的其余部分。但是对于无穷大，它是自动的。我希望对你有帮助。如果有什么不对的，请评论。

Answer 2

合并两个已排序的数组是一种线性复杂度操作。这意味着就 Big-O 表示法而言，它是 O(m+n)，其中 m 和 n 是两个排序数组的长度。所以当你说array length doesn't connect with the problem你的理解是正确的。无论两个排序数组的长度如何，这些数组的合并都涉及从每个排序数组中取出元素并将它们进行比较并将其中的一个复制到新数组（取决于您希望合并的排序数组按升序还是降序排列）并递增从中复制元素到新排序数组的数组。

Answer 3

解决这个问题的另一种方法是将每个数组视为有头和尾，并递归解决问题。这样，我们可以使用一个基本情况，两个大小为 1 的数组，对两个数组 m 和 n 的整体进行排序。由于两个数组都已排序，只需比较每个数组的两个头，然后将第一个元素添加到新创建的合并数组中，然后移动到该数组中的下一个元素。添加元素后，您的函数将再次调用自身。这将一直发生，直到两个数组之一为空。现在，您可以简单地将非空数组的剩余部分添加到合并数组的末尾，然后就完成了。我不确定您的教授是否允许您使用递归调用，但这种方法可以使编码更容易。运行时间仍然是 O(m+n)，因为您基本上是遍历两个数组一次。希望这可以帮助。