首页 > 试题广场 >

采用折半查找法查找长度为 n 的线性表时，每个元素的平均查找

[单选题]
采用折半查找法查找长度为 n 的线性表时，每个元素的平均查找长度为 。 
  • O(n2)
  • O(nlog2n)
  • O(n)
  • O(log2n)
查看正确选项
添加回答
智能车俱乐部看门大叔头像 智能车俱乐部看门大叔
时间复杂度无非就是while循环的次数！
总共有n个元素，
渐渐跟下去就是n,n/2,n/4,....n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,（是以2为底，n的对数）
所以时间复杂度可以表示O(h)=O(log2n)
发表于 2018-01-22 09:07:00 回复(0)
牛客487288286号头像 牛客487288286号

风风光光过眼云烟哈哈哈哈我就哈哈

编辑于 2019-05-09 15:00:12 回复(0)
小宝贝三岁i头像 小宝贝三岁i
查找长度为n的线性表
发表于 2019-02-27 14:53:32 回复(0)
MTDYKX头像 MTDYKX
d
发表于 2017-10-22 08:26:58 回复(0)
king熊头像 king熊
选择B
发表于 2017-08-13 17:22:50 回复(0)
提交观点

问题信息

查找
上传者：蜡蜡
难度：
5条回答 6318浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号