在Cormen的算法入门书中,我试图解决以下问题:
通过替换表明递归关系T(n)= T(n-1)+ n的解为O(n2)
(没有给出初始条件,这是问题的全文)
但是,我似乎无法找出正确的过程.教科书只是简单地触及它,我搜索过的大多数网站似乎都认为我已经知道了.如果有人可以给我一个简单的,一步一步的指南,甚至是一个链接,我将不胜感激.
对于踢球,这是我到目前为止的尝试:
T(n)<= c(n ^ 2)
<= c(n-1)^ 2 + n
<= c(n ^ 2 -2n +1)+ n(我很确定不是<c( N ^ 2))
再次感谢.
更新:这是我试图完成的方法的一个例子,以避免混淆.
证明解是O(nlog(n))
T(n)= 2T([n/2])+ n
替换方法要求我们证明T(n)<= cn*lg(n)可供选择常数c> 0.假设此约束适用于所有正m <n,其中m = [n/2],得到T([n/2])<= c [n/2]*lg([n/2] ).将其代入复发产生以下结果:
T(n)<= 2(c [n/2]*lg([n/2]))+ n
<= cn*lg(n/2)+ n
= cn*lg(n) - cn*lg(2)+ n
= cn*lg(n) - cn + n
<= cn*lg(n)
其中最后一步保持,只要c> = 1
我可以遵循这个逻辑很好,但是当我尝试复制上述问题中的步骤时,我会陷入困境.