首页 > 试题广场 >

二分查找的时间复杂度( )

[单选题]
二分查找的时间复杂度( )
  • O(N*log(N))
  • O(N)
  • O(log(N))
  • O(N^2)
推荐
C 二分法每次比较会去掉一半的数据,也就是说比较次数为n,数据为m个则2^n>=m,m=log(N),时间复杂度为O(log(N))
编辑于 2017-02-16 10:40:00 回复(0)
因为二分查找每次排除掉一半的不适合值,所以对于n个元素的情况:
一次二分剩下:n/2
两次二分剩下:n/2/2 = n/4
。。。
m次二分剩下:n/(2^m)
在最坏情况下是在排除到只剩下最后一个值之后得到结果,所以为
n/(2^m)=1;
2^m=n;
所以时间复杂度为:log2(n)
发表于 2017-04-26 16:49:36 回复(3)

第一次,在 个中找

第二次,在 个中找

第三次,在 个中找

.
.
.

第 k 次,在 个中找

假设在第 k 次找到了,则

每次执行一次,一共执行 k 次,则

发表于 2020-09-19 19:46:39 回复(0)
注意是二分查找不是排序
发表于 2019-08-04 17:35:03 回复(1)
我们可以理解为二叉树的深度,即O(log(N))
发表于 2017-09-08 23:53:44 回复(0)
每次减少一半,所以为log(n)
发表于 2022-03-31 20:26:13 回复(0)
二分法每次比较会去掉一半的数据,也就是说比较次数为n,数据为m个则2^n>=m,m=log(N),时间复杂度为O(log(N))
发表于 2020-06-18 10:54:56 回复(0)
C 二分法每次比较会去掉一半的数据,也就是说比较次数为n,数据为m个则2^n>=m,m=log(N),时间复杂度为O(log(N))
发表于 2020-04-10 11:13:13 回复(0)
C
每次使问题规模减小一半
发表于 2017-01-07 17:50:55 回复(0)
二分法,logN
发表于 2017-01-06 17:32:51 回复(0)