合并和排序两个已排序的数组，探究时间复杂度为O的细节。

Question

合并和排序两个已排序的数组，探究时间复杂度为O的细节。

javaarraysbig-o

3

这是一项学校作业。我不需要编程帮助，但由于我的老师没有提供帮助，所以我来到这里。

我被要求合并和排序两个已排序的数组，分别遵循以下两种情况：

1. 当两个数组的大小相等时； 2. 当两个数组的大小不同时。

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

然后我被要求计算时间复杂度（big(o)）。

我不需要代码，如果有人碰巧真正理解我的老师在问什么，请给我解决问题的提示。

- khuew

2

只需搜索，您就会找到如何合并两个已排序数组的方法。是的，如果您正确地执行它，大小不会成为问题，但是如果您选择错误的方法，我可以发现它可能会在不同大小的数组上失败，因此需要认真对待它。 - Shubham Srivastava

@VIPER已经正确地完成了它，在我的方法中大小并不重要。你能详细说明一下如何处理那些因为大小改变而失败的情况吗？谢谢！ - khuew

这篇文章应该会对你有所帮助 https://dev59.com/qmgu5IYBdhLWcg3w2KbM ，我认为两种情况并没有区别。情况1只是情况2的一种特殊情况，其中m和n相等。 - Pushpesh Kumar Rajwanshi

3个回答

1

合并两个已排序的数组是一种线性复杂度操作。这意味着在大O符号表示法方面，它是O(m+n)，其中m和n是两个已排序数组的长度。

因此，当您说“数组长度与问题无关”时，您的理解是正确的。无论两个已排序数组的长度如何，合并这些数组都涉及从每个已排序数组中取元素并进行比较，将其复制到新数组中（取决于您想要升序或降序的合并排序数组），并递增从中复制元素到新排序数组的数组计数器。

- Yug Singh

但我必须实现两种方法，其中一种需要相等的数组长度。我想不出一个依赖于 size1 = size2 的算法。我已经解决了需要不同数组大小的那个方法。 - khuew

由于长度在排序两个已排序数组时没有任何作用，因此您可以重复使用算法。 - Yug Singh

也许我的老师只是想向我们展示在大O表示法中大小并不重要。:/ 谁知道呢。 - khuew

1

是的，他可能对学生们想出解决方案感兴趣。在学习数据结构和算法时，思考非常重要，从问题中可以看出你的老师也希望如此。这将对你长期发展有好处。 - Yug Singh

1

另一种解决这个问题的方法是将每个数组视为具有头部和尾部，并递归地解决问题。通过这种方式，我们可以使用两个大小为1的数组作为基本情况，以遍历整个m和n两个数组。由于两个数组已经排序，只需比较每个数组的头部并将先出现的元素添加到新创建的合并数组中，然后移动到该数组中的下一个元素。在添加元素后，您的函数将再次调用自身。这将继续发生，直到其中一个数组为空为止。现在，您只需将非空数组剩余的内容添加到合并数组的末尾即可完成。

我不确定您的教授是否允许您使用递归调用，但这种方法可能会使编码更加容易。运行时间仍将为O（m + n），因为您基本上只需遍历两个数组一次。

希望这有所帮助。

- Cole Samaroo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Amin · Accepted Answer

学习而不是抄袭是非常好的。
正如您所建议的，情况1和情况2之间没有区别，但算法的最坏情况取决于您的解决方案。因此，我描述了我的解决方案（无代码），并给出了它的最坏情况。
在这两种情况下，数组必须以无限大结尾，因此将无限大添加到它们中。然后迭代每个数组的所有元素，在每个时间点，选择较小的一个并将其放入结果数组（合并两个数组）。
使用此解决方案，您可以轻松计算最坏情况。我们必须同时迭代两个数组，并将无限大添加到它们中，如果它们的长度为n和m，则我们的最坏和最佳情况是O(m + n)（您进行m + n + 2-1比较，并且-1是因为您不会比较两个数组的末尾，我的意思是无限大）。

但是为什么要在数组末尾添加无限大？因为我们必须复制带有一个额外空间的数组吗？这是一种方法，其最坏情况也是O(m + n)，因为需要复制数组。但是还有另一种解决方案。您可以进行比较，直到到达数组末尾，然后必须将未完全比较的其余数组添加到结果数组的末尾。但是使用无限大，这是自动完成的。

希望对您有所帮助。如果有什么不对的地方，请在评论中指出。