为什么将二进制搜索运行时间复杂度视为log2N [英] Why to consider binary search running time complexity as log2N

问题描述

有人说二进制搜索时，我说运行时间复杂度是 O（log n）吗？我在Google中搜索了它，得到了以下内容，

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,

您可以将搜索空间减半的次数与log < sub> 2 n。

我知道在数据结构中找到搜索关键字之前，我们会做一半的事情，但是为什么我们必须将其视为 log ₂ n ？我知道e ^x 是指数增长，因此 log ₂ n 是二元衰减。但是我无法根据对数定义的理解来解释二进制搜索。

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 成正比， n 的 m 看起来像这样：

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

log ₂ （n）= log ₂ （2 ^m ）

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

log ₂ （n）= m




换句话说：执行对大小为 n = 2 ^m 的数组进行二进制搜索所花费的时间与 m 成正比，或者等效地与 log _成正比2 （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屋！