如何计算二进制搜索的复杂性 [英] how to calculate binary search complexity

问题描述

我听到有人说，因为二进制搜索半区进行搜索，因此它的log（n）的算法，因为我不是从数学的背景需要输入我不能够涉及到它有人可以解释它在一个小细节？它必须做一些与数级数？

I heard somebody say that since binary search halfs the input required to search hence it is log(n) algorithms, Since I am not from a mathematics background I am not able to relate to it can somebody explain it in a little detail ? does it have to do something with the logarithmic series ?

推荐答案

下面更数学看到它，虽然不是非常复杂的方式。 IMO更清晰的非正式的：

Here a more mathematical way of seeing it, though not really complicated. IMO much clearer as informal ones:

现在的问题是，多少次你把N的2，直到你有1？这基本上等于在说，做一个二进制搜索（一半的元素），直到你找到它。在公式中，这将是这样的：

The question is, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be this:

1 = N / 2 ^X

1 = N / 2^x

乘以2 ^X ：

2 ^X = N

现在做日志 ₂ ：

登录 ₂ （2 ^X ）＆NBSP;＆NBSP;＆NBSP; =登录 ₂ ñ
  X *日志 ₂ （2）=登录 ₂ ñ
  X * 1＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; =登录 ₂ N

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

这意味着你可以将日志N次，直到你拥有了一切分歧。这意味着你必须划分日志N（做二进制搜索的步骤），直到你找到你的元素。

this means you can divide log N times until you have everything divided. Which means you have to divide log N ("do the binary search step") until you found your element.

这篇关于如何计算二进制搜索的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！