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

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗？Update the question所以堆栈溢出的值小于aa>。
我试图解决一个递归关系，以找出复杂的算法使用主定理和它的递归概念，我如何证明：
T(n) = T(n/2)+O(1)
是
T(n) = O(log(n)) ?
任何解释都会被告知的！!

最佳答案

你的复发是
T（n）=T（n/2）+O（1）
因为主定理与形式的重复有关
T（n）=aT（n/b）+nc
在这种情况下
A=1
b=2个
C=0
因为c=logba（因为0=log2 1），所以你在主定理的case two中，它的解是Θ（nc log n）=Θ（n0 logn）=Θ（logn）。
希望这有帮助！