经典指数          
原因
741
浏览数
0
收藏数
 

在一次 深度学习 的研讨会上, Andrew NG 出席了这次会议。遗憾的是,在这个会上的学者没有一个是他认识的,而出席会议的其他学者,每个人都认识 Andrew NG 。其他学者之间,有些是 A 认识 B B 不认识 A ,也有些事 A B 相互都不认识。我们要通过询问学者的方式,找出谁是 Andrew NG 。询问的时候可以任意找一个人 X ,问 X 是否认识 Y 。假设一共有 N 位学者出席会议,每次询问算一次操作,请问通过这种询问的方式确定谁是 Andrew NG 的最优复杂度是()

  • O(N*logN)
  • O(logN)
  • O(N)
  • O(N*N)

     举报   纠错  
 
切换
1 个答案
选a啊 分治策略。 两两比较,只有三种情况。 互不认识,都认识,一个认识另一个,ng只存在第三种情况被认识的那个。 树高最多为lgn,每层比较为n 所以是nlogn
 
切换
撰写答案
扫描后移动端查看本题