我听到有人说,由于二进制搜索将搜索所需的输入减半,因此它是log(n)算法。因为我没有数学背景,所以我不能与之产生共鸣。有没有人能更详细地解释一下?它一定要和对数级数有关吗?
发布于 2013-02-27 07:40:38
对于二分搜索,T(N) = T(N/2) + O(1) //递归关系
应用主定理计算递归关系的运行时复杂度: T(N) = aT(N/b) + f(N)
这里,a= 1,b=2 => log (以b为底)=1
另外,这里f(N) =n^clog^k(N) //k =0&c= log (以b为底)
因此,T(N) = O(N^c log^(k+1)N) = O(log(N))
发布于 2016-09-21 05:31:48
T(n)=T(n/2)+1
T(n/2)= T(n/4)+1+1
将(n/2)的值放在上面,这样T(n)=T(n/4)+1+1。。。。T(n/2^k)+1+1+1.....+1
=T(2^k/2^k)+1+1....+1,最大为k
=T(1)+k
当我们带着2^k=n
K= log n
因此时间复杂度为O(log )
发布于 2011-11-18 23:56:44
它不会将搜索时间减半,这不会使它成为log(n)。它以对数的方式减小它。考虑一下这一点。如果您在一个表中有128个条目,并且必须线性搜索您的值,那么平均可能需要64个条目才能找到您的值。这是n/2或线性时间。使用二进制搜索,您可以在每次迭代中消除1/2可能的条目,这样最多只需进行7次比较即可找到您的值( 128的对数基数2是7,或者2的7次方是128)。这就是二进制搜索的威力。
https://stackoverflow.com/questions/8185079
复制相似问题