用 O(log(nm)) 最坏情况合并两个有序数组

Question

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

编辑：我最初没有考虑过，但也许不可能在 O(log(n)) 中合并两个排序数组？实际目标是找到两个排序数组的中位数。有没有办法在不合并它们的情况下做到这一点？

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

Edit2：我将发布一个新问题，因为我意识到合并永远不会足够快。我认为我需要对每个数组执行二进制搜索以找到 log(n) 中的中位数。

原文由 Austin 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

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

我认为最好的方法是同时遍历每个数组，并在每次迭代时比较两个元素的值。如果一个小于另一个（如果您希望数组按降序排序），则将该元素复制到数组并增加该数组的索引指针，反之亦然。如果两个元素相同，您可以将它们都添加到新排序的数组中并增加两个指针。

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

那应该是 O(m+n)

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

您可以先找到两个排序数组的中位数（中间元素）并进行比较。如果它们相等，那么这就是中位数。如果第一个的中位数大于第二个的中位数，则您知道中位数必须在第一个数组的前半部分或第二个数组的后半部分，反之亦然，如果第一个的中位数小于第二个数组的中位数。

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

原文由 NickLamp 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

您可能正在考虑 选择算法。

对于排序的数据结构，找到中位数是 O(1)。对于未排序的数据结构（或数据被排序到两个逻辑分区的数据结构），运行时间为 O(n)。

您可能可以使用大规模并行缩减算法来实现它，但我认为这在运行时分析方面是作弊。

所以我不相信有一种算法可以将它降低到 O(n) 以下（或者，在你的情况下，O(n+m)）

原文由 Xirema 发布，翻译遵循 CC BY-SA 3.0 许可协议