algorithm - 你如何计算二分查找算法的大哦？

Question

我正在寻找数学证明，而不仅仅是答案。

Answer 1

recurrence relation of binary search is (在最坏的情况下)

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

使用 Master's theorem

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

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

我们有 f(n) = O(1) = O(n^log_ba)

=> T(n) = O(n^log_ba log₂ n)) = O(log₂ n)