高效的分治算法 [英] Efficient divide-and-conquer algorithm

问题描述

在一次政治活动中，介绍2个人确定他们是否代表同一政党.假设n个参与者中有一半以上代表同一方.我正在尝试找到一种有效的算法，该算法将使用尽可能少的介绍来识别该方的代表.

At a political event, introducing 2 people determines if they represent the same party or not. Suppose more than half of the n attendees represent the same party. I'm trying to find an efficient algorithm that will identify the representatives of this party using as few introductions as possible.

一种蛮力解决方案是在与会者阵列上保持两个指针，在O(n ² )时间内将n位与会者引入n-1个其他与会者.我不知道该如何改进.

A brute force solution will be to maintain two pointers over the array of attendees, introducing n attendees to n-1 other attendees in O(n²) time. I can't figure out how to improve on this.

正式

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.

希望这可以更好地解释问题.

Hopefully this explains the problem better.

推荐答案

可以在O(n)简介中使用

This can be done in O(n) introductions using the Boyer–Moore majority vote algorithm.

请考虑与会者的一些任意排序:A_1，A_2，...，A_n.在该算法中，您维护一个由m表示的存储元素".每当算法要检查当前元素(x)是否与存储的元素相同时，就引入这两个人，并相应地增加或减少计数器.最后存储的元素将是多数党的成员.然后，您可以对所有其他n-1个人进行另一次通行证，并将每个人介绍给这个已知的人，从而找到多数党的所有成员.

Consider some arbitrary ordering of the attendees: A_1, A_2, ..., A_n. In the algorithm, you maintain a 'stored element', denoted by m. Whenever the algorithm wants to check if the current element (x) is same as the stored element or not, you introduce those two people and increment or decrement the counter accordingly. The stored element at the end will be a member of the majority party. Then, you can do another pass over all the other n - 1 people, and introduce each of them to this known person and hence find all the members of the majority party.

因此，引言的总数为O(n).

Thus, the total number of introductions is O(n).

这篇关于高效的分治算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！