如何计算二进制搜索复杂度

Question

我听说有人说由于二进制搜索将搜索所需的输入减半,因此它是log(n)算法.由于我不是来自数学背景,所以我无法与之相关.有人可以更详细地解释一下吗？是否必须对对数系列做些什么？

Answer 1

这是一种更加数学化的方式来看待它,虽然并不是很复杂.IMO比非正式的更清楚:

问题是,你有多少次N除以2,直到你有1？这基本上是说,在你找到它之前做一个二进制搜索(一半元素).在一个公式中,这将是这样的:

1 = N/2 ^x

乘以2 ^x:

2 ^x = N.

现在做日志₂:

log ₂(2 ^x)= log ₂ N
x*log ₂(2)= log ₂ N
x*1 = log ₂ N.

这意味着您可以将日志分为N次,直到您将所有内容分开.这意味着您必须将log N("执行二进制搜索步骤")分开,直到找到您的元素.

Answer 2

对于二进制搜索,T(N)= T(N/2)+ O(1)//递归关系

应用Masters定理计算递归关系的运行时复杂度:T(N)= aT(N/b)+ f(N)

这里,a = 1,b = 2 => log(基数b)= 1

此外,这里f(N)= n ^ c log ^ k(n)// k = 0&c = log(基数b)

所以,T(N)= O(N ^ c log ^(k + 1)N)= O(log(N))

资料来源:http://en.wikipedia.org/wiki/Master_theorem

Answer 3

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 n)

Answer 4

它没有搜索时间的一半,也不会使它成为log(n).它以对数方式降低它.对此稍加思考.如果表中有128个条目并且必须线性搜索您的值,那么平均可能需要大约64个条目才能找到您的值.这是n/2或线性时间.使用二进制搜索,每次迭代消除1/2可能的条目,这样最多只需7次比较就可以找到你的值(128的基数2是7或2到7的幂是128.)这是二进制搜索的力量.

Answer 5

二进制搜索算法的时间复杂度属于O(log n)类.这称为大O表示法.你应该解释这个问题的方法是,给定一个大小为n的输入集,函数执行时间的渐近增长不会超过log n.

这只是正式的数学术语,以便能够证明陈述等.它有一个非常直接的解释.当n增长得非常大时,log n函数将超出执行函数所需的时间."输入集"的大小n只是列表的长度.

简单地说,二进制搜索在O(log n)中的原因是它在每次迭代中将输入集减半.在相反的情况下,更容易思考它.在x次迭代中,二进制搜索算法最多可以检查列表多长时间？答案是2 ^ x.由此我们可以看出,相反,平均而言,二进制搜索算法需要log2 n次迭代以获得长度为n的列表.

如果它为O(log n)而不是O(log2 n),那是因为简单地再次放置 - 使用大O符号常量不计算.

Answer 6

假设二分查找中的迭代在 k 次迭代后终止。\n在每次迭代时，数组都会除以一半。因此，令\xe2\x80\x99s 表示任意迭代时数组的长度为 n\n在迭代 1 时，

\n\n

Length of array = n\n

\n\n

在迭代 2 中，

\n\n

Length of array = n\xe2\x81\x842\n

\n\n

在第 3 次迭代中，

\n\n

Length of array = (n\xe2\x81\x842)\xe2\x81\x842 = n\xe2\x81\x8422\n

\n\n

因此，在迭代 k 之后，

\n\n

Length of array = n\xe2\x81\x842k\n

\n\n

另外，我们知道\n经过k次除法后，数组的长度变成1 \n因此

\n\n

Length of array = n\xe2\x81\x842k = 1\n=> n = 2k\n

\n\n

两边应用log函数：

\n\n

=> log2 (n) = log2 (2k)\n=> log2 (n) = k log2 (2)\nAs (loga (a) = 1)\n

\n\n

所以，

\n\n

As (loga (a) = 1)\nk = log2 (n)\n

\n\n

因此二分查找的时间复杂度为

\n\n

log2 (n)\n

\n