使用主定理求解递推式 T(n) = T(n / 2) + O(1)？ [关闭]

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

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

is

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

任何解释将不胜感激！

您的复发是

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

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

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

在这种情况下你有

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

Since c = log_ba (since 0 = log₂ 1), you are in case two https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Case_2_example of the Master Theorem, which solves to Θ(n^c log n) = Θ(n⁰ log n) = Θ(log n).

希望这可以帮助！