求一道简单题目的算法伪代码
首页/题库/261℃/2022-05-25 19:07:45
求一道简单题目的算法伪代码
在n个人中,只有一个人是名人(Celeberty),所有人都认识他而他不认识任何其他n-1个人,其他n-1个人相互是否认识是随机的,现在要一个算法来找出这个名人.
要求是:只能问某个人“你认识他吗”,或者说是问A认识B吗,答案只有Yes 或 No,不能问A和B是否相互认识,最重要的一点,大O符号要是O(n).
PS:我已经有一个算法,可是大O符号是O(n log (n)),求高手给个更好的算法.
优质解答:
可能的人k=第1人;
for(i=第二人;i不是最后一个人;i=下一个人)
{
if(k认识i==yes)
k=i
}
最后保留下来的一定是那个名人.
因为只有遇到名人,才能保证之后一定不会再碰见认识的人.
而在碰到名人之前,一定会遇到名人(假定你那随机之后一定有一个名人),
那么k就会指向名人.
有点像脑经急转弯.
你的方法应该是两两相比较,然后比较结果再比较的算法吧.
再问: 文字太多了,还是发图片吧。。。。
再答: 恩。你的解法就是我说的那种两两比较后,再把结果拿来比较。 我的直觉告诉我好像是nlog n的复杂度,符合T(N)=2T(n/2)+k的模型。 但你这么算也是对的,这算是O(n)的 算法。 但是你n的系数比我的大,而且应该还有很多数据交换。 其实完全可以向我那样只向一个方向问,那么你的最后询问次数也是n,而不是2n。 我还谈不上大神。。。不过确实晚上做事效率高些。 干扰少点,可以安心写代码~
我来回答修改/报错/举报内容!
猜你喜欢
- 英语翻译没有约定的守候我能为你写出缠绵的长诗只因对你有说不尽的情话我默默地守候你在咫尺 在天涯在咫尺 在天涯只因有我默默
- 物质的酸性强弱取决于哪些条件?
- 抛物线的顶点是坐标原点,对称轴是坐标轴,并且过点M(3,负4),求抛物线的方程
- 请问:扁鹊三兄弟这故事的出处是何经典?
- 分别说出中国经济、政治、思想文化近代化开始的标志性事件
- 我想要一个英文名开头可以是a.y,然后要有g(y也行),最后就是要有er【(ar也行)要连在一起】.还有最好不要太长.
- 控制性详细规划评审要达到怎样的深度
- we went to the cinema.
- she said she was going to look after him.(划线部分was going to)
- 什么叫抽样分布?给出三类重要分布的定义和抽样分布定理及其三个推论.
- 全称命题存在命题的否定
- 求一道选择题的答案,并说明理由