提一个关于排序算法的问题,请大佬解答一下:

一个无序整数数组长度为N(N>100),要判断M个不同的整数是否在数组里,当M大于( )时你就会优先将数组排列再进行判断?
A. 0
B. 2
C. 2log2N
D. 2N
#笔试题目#
全部评论
  感觉排除法一看就选C吧。。。错了不要打我
点赞 回复 分享
发布于 2019-07-10 21:19
假设每次查找的复杂读相同,在无序数组中查找复杂度为 O(N),有序数组中查找复杂度为 O(lgN),排序数组的复杂度为 O(N*lgN)。 那么在有序数组中查找M个数的复杂度为 O(M*N),在无序数组中查找M个数的复杂度为 O(M*lgN)。 也就是计算 M*N > M*lgN + N*lgN 时 M 的取值,M > N / ( N / lgN - 1 ) > lgN。 所以选 C。 错了请轻喷 🙃
点赞 回复 分享
发布于 2019-07-10 21:05

相关推荐

群星之怒:不是哥们,你就不好奇瘫痪三十年的老植物人是啥样的吗?
点赞 评论 收藏
分享
评论
点赞
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务