使用主定理求解递归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).

希望这可以帮助!