如何计算二进制search的复杂性
我听到有人说，由于二进制search所需的input减半，所以它是log（n）algorithm。 由于我不是来自math背景，我不能与之相关。 有人可以更详细地解释一下吗？ 它是否必须对对数级数做些什么？
在这里看到一个更加math的方式，虽然不是很复杂。 海事组织作为非正式组织更清晰：
问题是，你可以用N除以2，直到你有1？ 这实际上是说，做一个二分search（一半的元素），直到你find它。 在一个公式中，这将是：
1 = N / 2 ×
乘以2 x ：
2 x = N
现在做日志2 ：
log 2 （2 x ）= log 2 N
x * log 2 （2）= log 2 N
x * 1 = log 2 N
这意味着您可以将日志分为N次，直到您将所有内容分开为止。 这意味着你必须除以log N（“执行二进制search步骤”）直到find你的元素。
对于二进制search，T（N）= T（N / 2）+ O（1）//recursion关系
T（N）= aT（N / b）+ f（N）运用复杂关系的运算时间复杂度
这里，a = 1，b = 2 => log（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
它没有一半的search时间，这不会logging（n）。 它以对数forms降低。 对此稍加思考。 如果您在一个表中有128个条目，并且必须线性search您的价值，那么平均可能需要大约64个条目才能find您的价值。 这是n / 2或线性时间。 使用二分查找，每次迭代可以消除1/2个可能的条目，因此最多只需要7个比较就可以find您的值（128的基数2为7或2，7的幂为128）。二进制search的力量。
T（N）= T（N / 2）+1
T（n / 2）= T（n / 4）+ 1 + 1
把（n / 2）的值放在上面，这样T（n）= T（n / 4）+ 1 + 1。 。 。 。 T（N / 2 ^ k）的+ 1 + 1 + 1 ….. + 1
= T（2 ^ k / 2 ^ k）+ 1 + 1 …. + 1直到k
= T（1）+ K
正如我们采取2 ^ k = n
K = log n
所以时间复杂度是O（log n）
二进制searchalgorithm的时间复杂度属于O（log n）类。 这被称为大O符号 。 你应该理解的方式是给定一个大小为n的input集的函数执行所花费的时间的渐近增长不会超过log n 。
这只是正式的math术语，以便能够certificate陈述等。它有一个非常简单的解释。 当n变得非常大时，log n函数将增加执行该函数所需的时间。 “input集”的大小n只是列表的长度。
简而言之，二进制search在O（log n）中的原因是它在每次迭代中将input集合减半。 在相反的情况下考虑这一点更容易。 在x次迭代中，二进制searchalgorithm可以在多长时间内检查最大值？ 答案是2 ^ x。 由此我们可以看出，相反，平均来说，二分searchalgorithm需要对长度为n的列表进行log2n次迭代。
如果为什么它是O（log n）而不是O（log2 n），那是因为简单地再放一次 – 使用大O符号常量不计算。
这里是维基百科条目
如果你看看简单的迭代方法。 你只是消除了一半要search的元素，直到find你需要的元素。
以下是我们如何提出公式的解释。
说起初你有N个元素，那么你做的第一个尝试就是N / 2。 其中N是下界和上界的和。 N的第一次值将等于（L + H），其中L是第一个索引（0），H是您正在search的列表的最后一个索引。 如果你很幸运，你试图find的元素将在中间[例如。 您正在search列表{16,17,18,19,20}中的18，则计算⌊（0 + 4）/2⌋= 2，其中0是下限（L是数组第一个元素的索引） 4是上限（数组的最后一个元素的H – 索引）。 在上述情况下，L = 0和H = 4。现在2是您正在search的元素18的索引。 答对了！ 你find了
如果情况是不同的arrays{15,16,17,18,19}，但你仍然在寻找18，那么你不会是幸运的，你会做第一个N / 2（这是⌊（0 + 4）/ 2⌋= 2，然后在索引2处实现元素17不是您要查找的数字现在您知道在下次尝试search迭代方式时，您不必查找至less一半的数组。因此，基本上，您不要search以前search到的元素列表的一半，每次尝试查找在之前的尝试中找不到的元素。
所以最坏的情况是
[N] / 2 + [（N / 2）] / 2 + [（（N / 2）/ 2）] / 2 …..
即：
N / 2 1 + N / 2 2 + N / 2 3 + ….. + N / 2 x …
直到…你已经完成search，你试图find的元素在列表的末尾。
这表明最坏的情况是当你达到N / 2 × ，其中X是2 × = N
在其他情况下N / 2 x其中x是2 x <N x的最小值可以是1，这是最好的情况。
现在math上最糟糕的情况是什么时候的价值
2 x = N
=> log 2 （2 x ）= log 2 （N）
=> x * log 2 （2）= log 2 （N）
=> x * 1 = log 2 （N）
=>更正式的logging2 （N）+1⌋
Log2（n）是在二进制search中查找某些内容所需的最大search次数。 平均情况涉及log2（n）-1search。 以下是更多信息：
由于我们每次减less了一半的列表，所以我们只需要知道我们得到1的步骤，因为我们继续分两个列表。 在给定的计算中，x表示我们划分列表直到得到一个元素的时间数（在最差情况下）。
1 = N / 2x
2x = N
以log2
log2（2x）= log2（N）
x * log2（2）= log2（N）
x = log2（N）
二进制search通过将问题重复分成两半来工作，如下所示（详细内容省略）：
在[4,1,3,8,5]中查找3的示例
- 订购您的物品清单[1,3,4,5,8]
- 看中间的项目（4），
- 如果这是你正在寻找的，停止
- 如果更大，请看上半场
- 如果less了，看下半场
- 用新列表[1，3]重复步骤2，find3并停止
当你把问题分成两部分时，这是一个二元search。
search只需要log2（n）步骤来find正确的值。
如果你想了解algorithm的复杂性，我会推荐algorithm介绍 。
