algorithm - 使用主定理求解递归 T(n) = T(n / 2) + O(1)？

Question

我正在尝试解决递归关系以找出使用主定理及其递归概念的算法的复杂性，我如何证明：

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

是

T(n) = O(log(n)) ?

任何解释将不胜感激！！

Answer 1

你的复发是

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

由于主定理适用于形式的递归

T(n) = aT(n / b) + n ^c

在这种情况下，您有

• a = 1
• b = 2
• c = 0

由于 c = log _b a（因为 0 = log ₂ 1），你是主定理的情况二，它解决了 Θ(n ^c log n) = Θ(n ⁰ log n) = Θ(log n)。

希望这可以帮助！