为什么要考虑二进制搜索运行的时间复杂度为log2N [英] why to consider binary search running time complexity is as log2N

问题描述

有人能解释我当谈到二进制的搜索，我们说的运行时间复杂度的 O（log n）的的？我在谷歌搜索，并得到了下面，

Can someone explain me when it comes to "Binary" search we say the running time complexity is O(log n)? I searched it in Google and got the below,

的次数，可以减少一半的搜索空间的数目是相同的日志<子> 2 N

"The number of times that you can halve the search space is the same as log₂ n".

我知道我们减半，直到我们找到的数据结构中的搜索关键字，但是为什么我们要考虑它的日志 ₂ N 的？据我所知，电子 ^X 是指数增长等等的日志 ₂ N 的是二进制衰减。但我无法跨preT在我的对数定义的理解方面的二进制搜索。

I know we do halve until we find the search key in the data structure, but why we have to consider it as log₂ n? I understand that e^x is exponential growth and so the log₂ n is the binary decay. But I am unable to interpret the binary search in terms of my logarithm definition understanding.

感谢

推荐答案

认为它是这样的：

如果你能负担得起一半的东​​西的 M 的时候，（例如，你可以花得起时间成正比的 M 的），那么如何大阵你能负担得起搜索？

If you can afford to half something m times, (i.e., you can afford to spend time proportional to m), then how large array can you afford to search?

尺寸显然阵列的 2 ^M 的，对吧？

Obviously arrays of size 2^m, right?

所以，如果你可以搜索大小的数组的 N = 2 ^M 的，那么花费的时间是成正比的 M 的，解决 M 的的的 N 的是这样的：

So if you can search an array of size n = 2^m, then the time it takes is proportional to m, and solving m for n look like this:

N = 2 ^M

登录 ₂ （N）=登录 ₂ （2 ^M ）

log₂(n) = log₂(2^m)

登录 ₂ （N）= M


换句话说：大小的阵列上执行二进制搜索的 N = 2 ^M 的需要时间成正比的 M 的，或者等价地，比例为日志 ₂ （N）的。

log₂(n) = m


Put another way: Performing a binary search on an array of size n = 2^m takes time proportional to m, or equivalently, proportional to log₂(n).

这篇关于为什么要考虑二进制搜索运行的时间复杂度为log2N的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！