用O(log(n + m))最坏的情况合并两个排序的数组 [英] Merging Two Sorted Arrays with O(log(n+m)) Worst Case

问题描述

我可以使用哪种算法将两个排序后的数组合并为一个排序后的数组，其最坏情况下的时间复杂度为O(log(m + n))，其中n，m是数组的长度?我对算法的经验很少，但是我检查了合并排序，看来合并步骤的时间复杂度是O(n).是否有其他方法可以合并到O(log(n))中?

我最初没有考虑过，但是也许不可能在O(log(n))中合并两个排序的数组吗?实际目标是找到两个排序数组的中位数.有没有一种方法可以不合并它们呢?

我唯一的想法是，我读到合并两个二项式堆是O(log(n))，但是将数组变成二项式堆是O(n)，我想这样是行不通的. /p>

Edit2:我将发布一个新问题，因为我已经意识到合并永远不会足够快.我想我需要在每个数组上执行二进制搜索以找到log(n)中的中值.

解决方案

我认为没有一种算法可以在O(log(n+m))时间内合并两个数组.

当您考虑它时，这是有道理的.如果要创建一个新的n+m元素排序数组，则至少需要进行n+m个副本.没办法解决这个问题.

我认为最好的方法是同时迭代每个数组，并在每次迭代时比较两个元素的值.如果一个小于另一个(如果希望数组按降序排序)，则将该元素复制到该数组，并增加该数组的索引指针，反之亦然.如果两个元素相同，则只需将它们都添加到新排序的数组中，然后再将两个指针递增即可.

继续直到其中一个指针到达其各自数组的末尾，然后再将其复制到另一个数组的其余部分中.

应该是O(m+n)

关于您的编辑，有一种方法可以在log(n + m)时间内找到两个独立数组的中值.

您首先可以找到两个排序数组(中间元素)的中位数，然后进行比较.如果它们相等，则为中位数.如果第一个中位数大于第二个中位数，则您知道该中位数必须位于第一个数组的前半部分或第二个数组的后半部分，反之亦然，如果第一个中位数小于第二个数组.

此方法将您的搜索空间每次迭代减少一半，因此为log(n + m)

What kind of algorithm can I use to merge two sorted arrays into one sorted array with worst-case time complexity of O(log(m+n)) where n, m are the length of the arrays? I have very little experience with algorithms, but I checked out merge-sort and it seems that the time-complexity for the merging step is O(n). Is there a different approach to merge in O(log(n))?

Edit: I hadn't considered initially, but maybe it's not possible to merge two sorted arrays in O(log(n))? The actual goal is to find the median of two sorted arrays. Is there a way to do this without merging them?

The only idea I've had was I read that merging two binomial heaps is O(log(n)), but turning an array into a binomial heap is O(n) I think so that won't work.

Edit2: I'm going to post a new question because I've realized that merging will never work fast enough. I think instead I need to perform a binary search on each array to find the median in log(n).

解决方案

I don't think there is an algorithm that would merge two arrays in O(log(n+m)) time.

And it makes sense when you think about it. If you're trying to create a new sorted array of n+m elements you will need to do at least n+m copies. There is no way getting around that.

I think the best way would be to iterate through each array simultaneously and, at each iteration, compare the values of both elements. If one is less than the other (if you want the array sorted in descending order), then copy that element to the array and increment your indexing pointer for that array and vice versa. If the two elements are the same, you can just add them both into the newly sorted array and increment both pointers.

Continue until one of the pointers has reached the end of its respective array and then copy in the rest of the other array once one has.

That should be O(m+n)

Regarding your edit, there is a way to find the median of two separate arrays in log(n + m) time.

You can first find the median of the two sorted arrays (the middle element) and compare them. If they are equal, then that is the median. If the first's median is greater than the second's you know the median has to be in either the first half of the first array or the second half of the second array and vice versa if the first's median is less than the second's.

This method cuts your search space in half each iteration and is thus log(n + m)

这篇关于用O(log(n + m))最坏的情况合并两个排序的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！