"名人"算法的最佳解决方案

Question

在n人中," 名人 "被定义为 每个人都知道但不认识任何人的人.问题是识别名人,如果存在的话,只询问表格的问题," 对不起,你知道那边的那个人吗？ "(假设所有的答案都是正确的,甚至那个名人也会也回答.)目标是尽量减少问题的数量.

这个订单的解决方案是否少于明显的解决方案O(n^2)？

Answer 1

在这里使用名人问题的分析

蛮力解决方案.图表最多有n(n-1)边缘,我们可以通过询问每个潜在边缘的问题来计算它.此时,我们可以通过计算其indegree及其outdegree来检查顶点是否是接收器.这种蛮力解决方案提出了n(n-1) 问题.接下来,我们将展示如何在大多数3(n-1) 问题和线性位置执行此操作.

优雅的解决方案.我们的算法包括两个阶段:在消除阶段,我们消除除了一个人以外的所有人; 在验证阶段,我们检查这个剩下的人是否确实是名人.淘汰阶段保留了可能的名人名单.最初它包含所有人n .在每次迭代中,我们从列表中删除一个人.我们利用以下关键观察:如果人1知道人2,那么人1就不是名人; 如果人1不认识人2,那么人2不是名人.因此,通过询问人1是否了解人2,我们可以从可能的名人列表中消除任何人1或人2.人们说,我们可以反复使用这个想法消除所有人,只有一个人p.我们现在通过蛮力证实是否p是名人:对于每个其他人i,我们询问人p 是否认识他人i,并询问人们i是否认识他人p.如果人p总是回答否,而其他人总是回答是,那么我们就宣布人为p名人.否则,我们得出结论,这个群体中没有名人.

Answer 2

1. 将所有人分开.

2. 对于每一对(A,B),问A是否他知道B.

   • 如果答案是肯定的,A不能成为名人,丢弃他.
   • 如果答案是否定的,B不能成为名人,丢弃他.

   现在,只剩下一半人.

3. 从1开始重复,直到只剩下一个人.

成本O(N).

Answer 3

这是 O(N) 时间算法

1. 将所有元素压入堆栈。
2. 删除前两个元素（比如 A 和 B），如果 B 知道 A 而 A 不知道 B，则保留 A。
3. 删除A，B是彼此认识或彼此不认识

Answer 4

这个问题可以用O(N^2) 时间复杂度的图（入度和出度概念）解决。

我们还可以使用简单的两点概念在O(N) 时间和 O(1) 空间中解决这个问题。 我们将一次比较两个人，一个从头开始，另一个从最后开始，我们将把那个不能是名人的人排除在考虑之外。例如，如果有两个人 X 和 Y，并且 X 可以识别出 Y 人，那么 X 肯定不可能是名人，因为它知道该党内的某个人。另一种情况是 X 不认识 Y，在这种情况下，Y 不可能是名人，因为在聚会中至少有一个人不认识他/她。可以使用这种直觉两点的概念来找到这个聚会中的名人。

我在 algods 的 Youtube 上找到了一个很好的解释视频。

您可以参考此视频以获得更好的解释。

视频链接：

https://youtu.be/aENYremq77I