arrays - 两个有序数组联合中的第 k 个最小元素

Question

我无法理解这里的第三个算法，它是最好的 O(lg m + lg n)。 他们在代码中说如果 Ai < Bj => Ai < B(j-1)。那个怎么样 ？]

考虑到问题 O(lg m + lgn) 会更快还是 O(k. log (min(m,n)) ？

Answer 1

保持不变性i+j=k-1使我们处于几种可能的情况。如果我们找到了正确的i和j则意味着其中一个是第k 个元素。它尊重以下条件之一：

• 如果Bj-1 < Ai < Bj，则 Ai 必须是第 k 个最小的
• 否则，如果 Ai-1 < Bj < Ai，则 Bj 必须是第 k 个最小的。

如果没有，我们有，A[i]<B[j]但没有A[i]>B[j-1]=> 你问这怎么可能的情况。因此A[i] < B[j] => A[i] < B[j-1]，由于没有发生第一个条件。

问题的第二部分：

O(lg m + lgn) > O(k.log (min(m,n))

这是我的观点，我会告诉你为什么。如果m和n中的一个比另一个大很多（假设 n << m），我们将不得不比较：log m + log nwith k * log(n)。

为了平等，我们需要log m=(k-1)log n. 但是由于 k 是一个常数并且可以是一个很小的数字，我们假设 n << m ，这将导致log m > k* log n.

尽管如此，根据n和m，两种复杂度之间的差异可能很小。