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

Question

所以我很确定它是O(n)(但它可能不是？),但你如何用替换解决它？

如果假设T(n)<= c*n,那么归纳步骤是什么？

Answer 1

首先,我想清楚地假设Θ(1)= k,某些常数.

接下来,使用替换方法,我们得到

 T(n)=2T(n/2)+?(1)
     =2T(n/2)+k
     =2{2T(n/4)+k)+k
     =4T(n/4)+3k
     =...
     =n.T(1)+(n-1)k
     =n.k+(n-1)k
     =2nk-k
     =O(n).

如果你假设它T(n) <= c * n,你应该从T(1)开始并假设T(n)是正确的,然后通过使用T(n)的假设继续表明它对于T(n + 1)是正确的.

顺便说一下,你的假设是对的!