如何计算二进制搜索的复杂性

2018-06-14 01:22:04

我听到有人说，由于二分查找所需的输入减半，因此它是log（n）算法。由于我不是来自数学背景，我无法与之联系。有人可以更详细地解释它吗？它是否必须对对数级数做些什么？

这里看到一个更加数学的方式，虽然不是很复杂。海事组织作为非正式组织更清晰：

问题是，你可以将N除以2直到你有1次？这实际上是说，做一个二分搜索（一半的元素），直到你找到它。在一个公式中，这将是：

1 = N / 2x

乘以2x：

2x = N

现在做log2：

log2（2x）= log2 N
x * log 2（2）= log 2 N
x * 1 = log2 N

这意味着您可以将日志分为N次，直到您将所有内容分开为止。这意味着你必须除以log N（“执行二进制搜索步骤”）直到找到你的元素。

对于二元搜索，T（N）= T（N / 2）+ O（1）//递归关系

应用掌握定理计算递归关系的运行时间复杂度：T（N）= aT（N / b）+ f（N）

这里，a = 1，b = 2 => log（a base b）= 1

此外，这里f（N）= n ^ c log ^ k（n）// k = 0＆c = log（a base b）

所以，T（N）= O（N ^ c log ^（k + 1）N）= O（log（N））

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

它没有一半的搜索时间，这不会使其记录（n）。它以对数形式减少。对此稍加思考。如果您在表格中有128个条目并且必须线性搜索您的价值，那么平均可能需要大约64个条目才能找到您的价值。这是n / 2或线性时间。通过二分法搜索，每次迭代可以消除1/2个可能的条目，例如，最多只需要7次比较就可以找到您的值（128的基准2为7或2，7的功率为128）。这是二进制搜索的力量。

链接地址: http://www.djcxy.com/p/40027.html

上一篇: how to calculate binary search complexity

下一篇: Is there a way to tell whether a subroutine has runtime log(n)?