你如何计算二进制搜索算法的大哦？

Question

我正在寻找数学证明,而不仅仅是答案.

Answer 1

二元搜索的递归关系(在最坏的情况下)

T(n) = T(n/2) + O(1)

使用硕士定理

• n是问题的大小.
• a是递归中的子问题数.
• n/b是每个子问题的大小.(这里假设所有子问题的大小基本相同.)
• f(n)是在递归调用之外完成的工作的成本,其中包括划分问题的成本和将解决方案合并到子问题的成本.

这里a = 1,b = 2和f(n)= O(1)[常数]

我们有f(n)= O(1)= O(n ^{log _b a})

=> T(n)= O(n ^{log _b a} log ₂ n))= O(log ₂ n)

Answer 2

证明非常简单:如果您还没有找到要查找的项目,则每次递归时您将剩余项目的数量减半.因为你只能在最多log ₂(n)次递归地将数字n分成两半,这也是递归的边界:

2·2·...·2·2 = 2 ^X ≤ Ñ ⇒登录₂(2 ^X)= X ≤日志₂(Ñ)

这里x也是递归的数量.并且当地成本为O(1 ),总共为O(log n).