3

这是问题：

有5个排序列表A，B，C，D，E，它们的长度相同。问题是找到一种算法，可以在 O(logn) 时间内对这 5 个列表进行中位数。我正在考虑一个一般性的想法，但我无法弄清楚它所需要的确切复杂性。

假设 A,B,C,D,E 的中位数是 a,b,c,d,e。我们有a<b<c<d<e。很明显，我可以丢弃数组 A 的前半部分和数组 E 的后半部分。现在我有 5 个新数组：B、C、D 保持不变，每个都有 n 个数字；A' 和 E' 各有 n/2 个数字。然后我将 A' 和 E' 的中位数计算为 a' 和 e'，将它们与 b、c、d 进行比较。如果 5 个中位数的新顺序是a'<b<e'<c<d，那么我通过去掉 a' 的前半部分（n/4 个数字）和数组 D 的最后 n/4 个数字，因为我们需要在最后的两边扔掉相等的数字中位数。过程继续...

我有一种感觉，算法是O(logn)。但我不知道确切的证据。在第一个 logn 步骤中，我们肯定可以将候选数减少到 3n，将 5 个列表的所有剩余数字相加。第一次我们踢出 n 个号码，第二次踢出至少 n/2 个号码，第三次踢出 n/4 个号码，以此类推。但是，在我得到 3n 个剩余数字后，我不知道如何分析。

这个算法真的可以给我 O(logn) 吗？

4

1 回答 1

2

是的，它实际上可以。看看那些说法

  • 只有当我们有一个列表时，我们才能得到最终结果。除非我们至少有两个列表，否则我们不能谈论这个。
  • 我们将算法的每一步都减少了一半的列表。如果列表中只有一个元素，我们将删除整个列表。
  • 让我们数一数，删除列表需要多少步骤。在第一次删除时，我们将删除 n/2 个项目，第二个 - n/4 以此类推，直到剩下一个元素，当我们最终删除列表时。这将需要 log(n) 操作（不知道它是真的 log(n) 还是 log(n)+1 但在这两种情况下都是 O(log(n)) ）。
  • 所以，我们需要消除5个列表（在最后一个列表中求中位数的操作可以推广到减少列表的操作）。消除其中一个需要 O(log(n))，所以我们也将在 O(log(n)) 中完成所有工作，因为 5 是常数。
于 2012-01-30T02:10:09.700 回答