问题是：
有 5 个排序列表 A、B、C、D、E，其长度 n 相同。问题是找到一种算法，可以在 O(logn) 时间内对这 5 个列表求中值。我正在考虑一个总体想法，但我无法弄清楚它所需的确切复杂性。
假设A、B、C、D、E的中位数为a、b、c、d、e。我们有a。显然，我可以扔掉数组 A 的前半部分和数组 E 的后半部分。现在我有 5 个新数组：B、C、D 保持不变，每个都有 n 个数字； A' 和 E' 各还剩下 n/2 个数字。然后，我将 A' 和 E' 的中位数计算为 a' 和 e'，并将它们与 b、c、d 进行比较。如果 5 个中位数的新顺序是 a'，那么我会遍历 a' 的前半部分（n/4 个数字）和最后一个 n/数组 D 的 4 个数字，因为我们需要扔掉最终中位数两边相等的数字。这个过程继续下去……
我有一种感觉，算法是O(logn)。但我不知道确切的证据。在第一个 logn 步骤中，我们肯定可以将候选数字减少到 3n，将 5 个列表的所有剩余数字相加。第一次我们踢出 n 个数字，第二次至少踢出 n/2 个数字，第三次踢出 n/4 个数字，依此类推。但是，我不知道在得到剩余的3n个数字后如何分析。
这个算法真的能给我 O(logn) 吗？
Here is the question:
There are 5 sorted list A,B,C,D,E, which has the same length n. The question is to find an algorithm that can median of this 5 list in O(logn) time. I am thinking of a general idea but I could not figure out the exact complexity it takes.
Assume the median of A,B,C,D,E is a,b,c,d,e. And we have a<b<c<d<e. It is obvious that I could throw away the first half of array A and the last half of array E. Now I have 5 new arrays: B,C,D stay the same, each has n numbers; A' and E' each has n/2 numbers left. I then compute the median of A' and E' as a' and e', compare them to b,c,d. If the new order of 5 medians is a'<b<e'<c<d, then I through away the first half of a' (n/4 numbers) and the last n/4 numbers of array D, because we need to throw away equal numbers on both sides of the final median. The process continue...
I have a kind of feeling that the algorithm is O(logn). But I don't know the exact proof. In the first logn steps, we can surely reduce the candidate numbers to 3n, adding up all the remaining numbers of the 5 lists. The first time we kick out n numbers, the second time at least n/2 numbers, the third time n/4 numbers and so on. However, I don't know how to analysis after I get 3n remaining numbers.
Can this algorithm actually give me O(logn)?
发布评论
评论（1）
是的，确实可以。只要看一下这些陈述，
Yes, it actually can. Just look at those statements