algorithm - 在一组人中找到“星”的算法的时间复杂度

我遇到了一个问题，要求在一组正常人中找到一颗星星。明星的定义是“谁都不认识，但每个人都认识他们”。输入是一个由 n 个人组成的数组，你可以做的基本测试是问一个人 i“你认识 j 人吗”，如果他们认识他，他们回答“真”，如果不认识他，则回答“假”。问最少的问题。

我为这个算法找到的最坏情况的最佳解决方案是 O(nlog) （你问一个人是否认识他们 i+1 之后的人，如果他们知道，你将他们从潜在明星中删除，如果不是，你将 i+1 从潜在明星中移除，每次通过阵列时，我可以将潜在明星的数量减半）但是练习说“证明它可以在最坏的情况下在 O(n) 中完成

标签： algorithmtime-complexity

明星的定义是“一个不认识的人，但每个人都认识他们

按照这个定义，这群人中最多只能有一个“明星”。如果有不止一颗星星，那么他们都必须知道另一颗，否则另一颗就不是一颗星星，那么他们自己就不是星星。

因此，有两个子问题。

如果这样的人不止一个，就没有明星；如果只有一个这样的人：

第一部分可以用你提出的算法来完成。不管你问A是否知道B，C是否知道D等等，或者你再问A或B的“赢家”是否知道C等等：因为你每次询问时都会删除一个“候选人”，您最多需要 O(n) 步，而不是 O(nlogn)。在那之后，你只剩下一个潜在的明星，可以做第二步，这是一个简单的循环，遍历组中的所有其他人。

两个步骤的时间复杂度为 O(n)，总共（仍然）O(n)。