java - 使用大 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) 也用于复制数组。但还有另一种解决方案。您可以比较直到到达数组的末尾，然后您必须添加未完全与结果数组末尾进行比较的数组的其余部分。但对于无穷大，它是自动的。

希望对你有所帮助。如果有什么不对的地方，请评论。