明星群众问题及思考

明星群众问题及思考

题目：有n-1个群众和1个明星，群众两两间可能认识也可能不认识，但是群众都认识明星，明星不认识其他任何人。现在每次询问一个人是否认识另一个人的时间复杂度是O(1)，要求找出明星的时间复杂度。

分析：这是一道老题，关键点在只有一个明星。首先分析一次询问的效果。is A 认识 B? (yes) A不是明星，B可能是明星 : (no) A可能是明星，B是群众。所以一次询问可以确定一个人。总共有n个人，那么当然是O(n)啦。这类时间复杂度的问题一般都有一个O(1)的操作，看看这个操作有什么信息量，就可以很快确定了。

例如，如果一次询问可以知道他认识的人和不认识的人，那么就采用分治的方法了。时间复杂度就是O(log(n))，有这种场景的。

如果有2个明星呢？明星之间互不认识。那么还是O(n)，因为找到一个明星之后询问其他所有人，选出不认识的

如果x个呢？当然也是O(n)啦。

网址：明星群众问题及思考 http://c.mxgxt.com/news/view/636105

相关内容

经过李易峰一事之后，明星声明失去公信力，这10个问题值得思考！
脱粉最多的明星，现象、原因及思考
我国明星广告代言存在的问题及对策研究
明星问题
吃瓜群众黑料泄密：社交媒体再曝明星私生活，网友热议背后真相与隐私权问题引发关注
军人婚恋现状问题的思考
明星怎么成了“问题人群”？
“日本应思考如何处理历史问题”
黑料网与明星热点，吃瓜群众的狂欢与真相探寻
高考作文导写：“饭圈文化”作文（附：文题详解及范文点评）

随便看看