二分查找算法的big oh是如何计算的？

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_ba< /sup>)}

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

Answer 2

证明非常简单：如果您还没有找到您要查找的项目，则每次递归都会将剩余项目的数量减半。由于你最多只能将一个数 n 递归地分成两半 log₂(n) 次，这也是递归的边界:

2·2·…·2·2 = 2^x ≤ n ⇒ log₂(2 ^x) = x ≤ log₂(n)

这里 x > 也是递归次数。本地成本为 O(1)，总共为 O(log n)。