algorithm - "celebrity"算法的最优解

Question

在 n 人中，“名人”被定义为某人人尽皆知，却无人知晓。这问题是识别名人，如果有的话，通过询问仅以形式提问，“对不起，你认识这个人吗那边？”(假设所有答案都是正确的，甚至那个名人也会回答。)目标是尽量减少问题的数量。

这里有没有比明显的O(n^2)阶数小的解？

Answer 1

利用名人问题的分析here

Brute-force solution. The graph has at most n(n-1) edges, and we can compute it by asking a question for each potential edge. At this point, we can check whether a vertex is a sink by computing its indegree and its outdegree. This brute-force solution asks n(n-1) questions. Next we show how to to do this with at most 3(n-1) questions and linear place.

An elegant solution. Our algorithm consists of two phases: in the elimination phase, we eliminate all but one person from being the celebrity; in the verification phase we check whether this one remaining person is indeed a celebrity. The elimination phase maintains a list of possible celebrities. Initially it contains all n people. In each iteration, we delete one person from the list. We exploit the following key observation: if person 1 knows person 2, then person 1 is not a celebrity; if person 1 does not know person 2, then person 2 is not a celebrity. Thus, by asking person 1 if he knows person 2, we can eliminate either person 1 or person 2 from the list of possible celebrities. We can use this idea repeatedly to eliminate all people but one, say person p. We now verify by brute force whether p is a celebrity: for every other person i , we ask person p whether he knows person i , and we ask persons i whether they know person p . If person p always answers no, and the other people always answer yes, the we declare person p as the celebrity. Otherwise, we conclude there is no celebrity in this group.