高效的分治算法

Question

在政治活动中，介绍两个人决定他们是否代表同一政党。假设n个与会者中有一半以上代表同一方。我正试图找到一种有效的算法，通过尽可能少的介绍来识别这个政党的代表。

暴力解决方案是在参与者阵列上维护两个指针，在O(n²(时间内将n个参与者引入n-1个其他参与者。我想不出如何改进这一点。

编辑：正式，

You are given an integer n. There is a hidden array A of size n, such that more than half of the values in A are the same. This array represents the party affiliation of each person.
You are allowed queries of the form introduce(i, j), where i≠j, and 1 <= i, j <= n, and you will get a boolean value in return: You will get back 1, if A[i] = A[j], and 0 otherwise.
Output: B ⊆ [1, 2. ... n] where |B| > n/2 and the A-value of every element in B is the same.

希望这能更好地解释问题。

Answer 1

这可以在O(n(介绍中使用Boyer–Moore多数投票算法来完成。

考虑与会者的一些任意排序：A_1，A_2。。。，A_ n。在算法中，你维护一个"存储的元素"，用m表示。每当算法想检查当前元素(x(是否与存储的元素相同时，你引入这两个人，并相应地递增或递减计数器。最后存储的元素将是多数党的成员。然后，你可以对所有其他n-1人进行另一次筛选，并将他们每个人介绍给这个已知的人，从而找到多数党的所有成员。

因此，引入的总数为O(n(。