问题描述:
求一道简单题目的算法伪代码
在n个人中,只有一个人是名人(Celeberty),所有人都认识他而他不认识任何其他n-1个人,其他n-1个人相互是否认识是随机的,现在要一个算法来找出这个名人.
要求是:只能问某个人“你认识他吗”,或者说是问A认识B吗,答案只有Yes 或 No,不能问A和B是否相互认识,最重要的一点,大O符号要是O(n).
PS:我已经有一个算法,可是大O符号是O(n log (n)),求高手给个更好的算法.
在n个人中,只有一个人是名人(Celeberty),所有人都认识他而他不认识任何其他n-1个人,其他n-1个人相互是否认识是随机的,现在要一个算法来找出这个名人.
要求是:只能问某个人“你认识他吗”,或者说是问A认识B吗,答案只有Yes 或 No,不能问A和B是否相互认识,最重要的一点,大O符号要是O(n).
PS:我已经有一个算法,可是大O符号是O(n log (n)),求高手给个更好的算法.
问题解答:
我来补答展开全文阅读