通过替换求解递归T(n)= 2T(n/2)+Θ(1) [英] Solving recurrence T(n) = 2T(n/2) + Θ(1) by substitution

问题描述

所以我很确定它是O(n)(但是可能不是吗?)，但是如何用替代来解决呢?

So I am pretty sure it is O(n) (but it might not be?), but how do you solve it with substitution?

如果假设T(n)< = c * n，归纳步骤是什么?

If you assume T(n) <= c * n, what is the induction steps?

推荐答案

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

First of all,I'd like to assume clearly that Θ(1)=k,some constant.

接下来，使用替代方法进行操作，我们得到

Next,proceeding using substitution method, we get

 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)的假设.

If you assume it as T(n) <= c * n,you should start with T(1) and assume for T(n) to be correct,and then proceed to show that it is correct for T(n+1) by using the assumption for T(n).

顺便说一句，您的假设是正确的！

这篇关于通过替换求解递归T(n)= 2T(n/2)+Θ(1)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！