我知道如何处理像这样的递归:
T(n) = 2T(n/2) + n
在这种情况下,我会猜测答案是O(nlogn),然后使用归纳法来证明它。但是,对于这个问题中的Θ(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))
T(1)=T(1/2)+Θ(1)
,接下来是 T(1/2)=0;
所以 T(1)=Θ(1)=常数,假设为1
。 - Am_I_Helpful