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

我听到有人说，因为二进制搜索一半的输入需要搜索，因此它是日志(n)算法。因为我没有数学背景，所以我不能理解它。有人能解释得更详细一点吗？它和对数级数有什么关系吗？

283629 次浏览
小开

Something log2(n) + 1 something 是在二进制搜索中查找所需的最大比较次数。平均情况下进行大约 log2(n)-1比较。以下是更多信息:

Http://en.wikipedia.org/wiki/binary_search#performance

小开

它没有一半的搜索时间，这不会使它日志(n)。它是对数减少的。好好想想。如果一个表中有128个条目，并且必须线性搜索您的值，那么平均大约需要64个条目才能找到您的值。这是 n/2或线性时间。使用二进制搜索，每次迭代消除1/2可能的条目，这样最多只需要7个比较就可以找到您的值(基于128的对数2是7，或者2的7次方是128)这就是二进制搜索的力量。

小开

二进制搜索的工作原理是反复地将问题一分为二，如下所示(细节省略) :

示例查找[4,1,3,8,5]中的3

  1. 订购你的物品清单[1,3,4,5,8]
  2. 看中间的项目(4) ,
    • 如果这就是你想要的，停下
    • 如果它更大，看看前半部分
    • 如果少了，看看下半场
  3. 使用新列表[1,3]重复步骤2，找到3并停止

当你把问题分成2部分时，这是一个 双性恋-nary 搜索。

搜索只需要 log2(n)步骤就可以找到正确的值。

如果您想了解算法的复杂性，我建议使用 算法入门。

小开

二进制搜索算法的时间复杂度属于 O (logn)类。这叫做 大 O 符号。你应该这样解释: 给定一个大小为 n 的输入集，函数执行所需时间的渐近增长不会超过 log n。

这只是正式的数学术语，以便能够证明陈述等。它有一个非常直接的解释。当 n 变得非常大时，logn 函数将超过执行该函数所需的时间。“ input set”的大小 n 就是列表的长度。

简单地说，二进制搜索在 O (logn)中的原因是它在每次迭代中将输入集减半。在相反的情况下更容易思考这个问题。在 x 次迭代中，二进制搜索算法最大可检查多长列表？答案是2 ^ x。从这里我们可以看到相反的情况，对于长度为 n 的列表，二进制搜索算法平均需要 log2 n 次迭代。

如果为什么是 O (logn)而不是 O (log2n) ，那是因为简单地再放一次——使用大的 O 符号常量不算数。

小开
最佳答案

这里有一个更加数学化的方法来看待它，虽然不是真正复杂的:

问题是，N 除以2到得到1的次数是多少？这实际上是说，进行二进制搜索(一半的元素) ，直到找到它。公式是这样的:

1 = N/2X

乘以2X:

2X = N

现在做 log2:

Log2(2X) = log2N
X * log2(2) = log2 N
X * 1 = log2N

这意味着您可以除以 log N 次，直到将所有内容都除完为止。这意味着您必须除以 log N (“执行二进制搜索步骤”) ，直到找到您的元素。

小开

对于二进制搜索, T (N) = t (N/2) + o (1)//递回关系式

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

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

同样，这里 f (N) = n ^ c log ^ k (n)//k = 0 & c = log (a 基 b)

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

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

小开

这是 维基百科的入口

如果你看看简单的迭代方法。您只是消除了要搜索的元素的一半，直到您找到所需的元素。

下面是我们如何得出这个公式的解释。

假设一开始你有 N 个元素，然后你要做的是 作为第一次尝试。其中 N 是下界和上界之和。N 的第一个时间值等于(L + H) ，其中 L 是第一个索引(0) ，H 是您正在搜索的列表的最后一个索引。如果你幸运的话，你试图找到的元素会在中间[例如。在列表{16,17,18,19,20}中搜索18，然后计算 something (0 + 4)/2 something = 2，其中0是下界(数组第一个元素的 L- 索引) ，4是上界(数组最后一个元素的 H- 索引)。在上面的情况下，L = 0，H = 4。现在2是您正在搜索的元素18的索引。找到了！你找到了。

如果情况是一个不同的数组{15,16,17,18,19} ，但是你仍然在搜索18，那么你就不会那么幸运了，你会做第一个 N/2(即 something (0 + 4)/2 something = 2，然后意识到索引2处的元素17不是你要找的数字。现在您知道，在下一次尝试搜索迭代方式时，您不必查找至少一半的数组。你的搜寻工作减半了。所以基本上，每次尝试找到在前一次尝试中未能找到的元素时，都不会搜索先前搜索的元素列表的一半。

所以最坏的情况是

[ N ]/2 + [(N/2)]/2 + [((N/2)/2)]/2... ...
即:
N/21 + N/22 + N/23 + ... ... + N/2X... ...

直到... 您完成搜索，您试图找到的元素位于列表的末尾。

这表明最坏的情况是当你达到 N/2X，其中 x 等于2X = N

在其他情况下，N/2X，其中 x 使得2X < N X 的最小值可以是1，这是最好的情况。

现在数学上最糟糕的情况是
2X = N
= > log2(2X) = log2(N)
= > x * log2(2) = log2(N)
= > x * 1 = log2(N)
= > 更正式的 something log2(N) + 1 something

小开

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)

小开

因为我们每次都把一个列表减半，所以我们只需要知道，当我们把一个列表除以二的时候，我们有多少步得到1。在给定的计算中，x 表示除一个列表直到得到一个元素的时间(在最坏的情况下)。

1 = N/2x

2x = N

拍摄日志2

Log2(2x) = log2(N)

X * log2(2) = log2(N)

X = log2(N)

小开 
ok see this
for(i=0;i<n;n=n/2)
{
i++;
}
1. Suppose at i=k the loop terminate. i.e. the loop execute k times.


2. at each iteration n is divided by half.


2.a n=n/2                   .... AT I=1
2.b n=(n/2)/2=n/(2^2)
2.c n=((n/2)/2)/2=n/(2^3)....... aT I=3
2.d n=(((n/2)/2)/2)/2=n/(2^4)


So at i=k , n=1 which is obtain by dividing n  2^k times
n=2^k
1=n/2^k
k=log(N)  //base 2
小开

T (N) = T (N/2) + 1

T (N) = T (N/2) + 1 = (T (N/4) + 1) + 1

...

T (N) = T (N/N) + (1 + 1 + 1 + ... + 1) = 1 + logN (基数2 log) = 1 + logN

因此二进制搜索的时间复杂度为 O (logN)

小开

让我举个例子来说明一下。

为了简单起见，我们假设一个数组中有32个元素，按照排序顺序，我们使用二进制搜索来搜索一个元素。

123456... 32

假设我们要找的是32号。 在第一次迭代之后，我们将剩下

17181920... . 32

在第二次迭代之后，我们将只剩下

25262728... 32

在第三次迭代之后，我们将只剩下

29303132

在第四次迭代之后，我们将剩下

3132

在第五次迭代中，我们将找到值32。

所以，如果我们把它转换成一个数学方程，我们会得到

(32X (1/25)) = 1

= > nX (2K) = 1

= > (2K) = n

= > k log22 = log2n

= > k = log2n

这就是证据。

小开

假设二进制搜索中的迭代在 k 次迭代后终止。 在每次迭代中，数组被除以一半。所以我们假设数组在任何迭代中的长度都是 n 在第1次迭代中,

Length of array = n

在第2次迭代中,

Length of array = n⁄2

在第3次迭代中,

Length of array = (n⁄2)⁄2 = n⁄22

因此，在迭代 k 之后,

Length of array = n⁄2k

而且，我们知道 K 师之后是 数组的长度变为1 因此

Length of array = n⁄2k = 1
=> n = 2k

在两边都应用 log 函数:

=> log2 (n) = log2 (2k)
=> log2 (n) = k log2 (2)
As (loga (a) = 1)

所以,

As (loga (a) = 1)
k = log2 (n)

因此二进制搜索的时间复杂度是

log2 (n)
小开

下面是使用主定理和可读的 LaTeX 的解决方案。

对于二进制搜索递回关系式中的每个循环，我们将问题转化为一个子问题，运行时为 T (N/2)。因此:

T(n) = T(n/2)+1

代入主定理，我们得到:

T(n) = aT(n/b) + f(n)

现在，因为 < img src = “ https://i.stack.imgur.com/VNckf.gif”alt = “ logba”> < img src = “ https://i.stack.imgur.com/VNckf.gif”alt = “ logba”> 是0，f (n)是1，我们可以使用主定理的第二种情况，因为:

f(n) = O(1) = O(n0) = O(nlogba)

这意味着:

T(n)=O(nlogbalogn) = O(n0logn) = O(logn)

小开

我们可以建立一个递回关系式 T (n) = T (n/2) + 1

T (n/2) = T (n/4) + 1 因此 T (n) = T (n/4) + 2

T (n/4) = T (n/8) + 1 因此 T (n) = T (n/8) + 3

我们可以建立关系

T (n) = T (n/(2 ^ k)) + k ——————我们称之为方程1

我们继续扩张，我们将达到一个点

2 ^ k = n ，左右对数

Log (2 ^ k) = log (n)

因此 K = log (n)
把 k 的这个值放到方程1中

T (n) = T (n/(2 ^ (log (n))) + log (n)

因此 T (n) = T (n/n) + log (n) 因此 T (n) = T (1) + log (n)

因此 T (n) = log (n)


提交答案