如何计算二分查找复杂度 [英] how to calculate binary search complexity

问题描述

我听到有人说，由于二分搜索将搜索所需的输入减半，因此它是 log(n) 算法.由于我不是数学背景，我无法与之相关.有人可以更详细地解释一下吗?和对数级数有关系吗?

I heard somebody say that since binary search halves the input required to search hence it is log(n) algorithm. Since I am not from a mathematics background I am not able to relate to it. Can somebody explain it in a little more 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

乘以2^x:

2^x = N

现在做日志₂:

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

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

这意味着您可以将日志划分 N 次，直到将所有内容都划分完毕.这意味着您必须对 log 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屋！