通过替换解决递归式T(n) = T(n/2) + Θ(1)

Question

我知道如何处理像这样的递归：

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

在这种情况下，我会猜测答案是O(nlogn)，然后使用归纳法来证明它。但是，对于这个问题中的Θ(1)，让我有些困惑。你会怎么做呢？如果您能提供归纳步骤，那就太好了。

非常感谢！

- evenodd

---

看起来对我来说是log n。只需替换，然后再次替换。 - gnasher729

Answer 1

尝试递归替换该值。

T(n) = T(n/2) + Θ(1)
 = (T(n/4) + Θ(1)) + Θ(1)  = T(n/4) + Θ(1) + Θ(1)  = T(n/4) + 2*Θ(1)
 = (T(n/8) + Θ(1)) + 2*Θ(1)= T(n/8) + 3*Θ(1)
 = T(n/16) + 4*Θ(1)
 = T(n/32) + 5*Θ(1) [ T(n/2^5) + 5*Θ(1) ]
 .                                           
 .                                           
 = T(1) + log2(n)*Θ(1)
 = O(log2(n))

- Haris

---

寻找 T(n) = T(n/2) + Θ(1) - evenodd

@GabeJacobs，根据您的问题进行了编辑。请确认。 - Haris

请添加--->T(1)=T(1/2)+Θ(1)，接下来是 T(1/2)=0; 所以 T(1)=Θ(1)=常数，假设为1。 - Am_I_Helpful