求解递归关系:T(n)= T(n-1)+ T(n/2)+ n

Question

求解:T(n)= T(n-1)+ T(n/2)+ n.

我试图解决这个使用递归trees.There两个分支T(n-1),并T(n/2)分别.T(n-1)将进一步深入.所以我们得到了O(2^n).这个想法是否正确？

Answer 1

不,你的想法不正确.复杂性O(n)也是我必须承认这个问题很难.

这是一个解决方案.T(n) = T(n-1) + T(n/2) + n.因为你计算的东西非常大n,比n-1几乎一样n.所以你可以把它重写为T(n) = T(n) + T(n/2) + n

在这里我犯了一个错误,错误的解决方案开始了:

是的T(n) = 1/2 * T(n/2) + n/2.如您所见,这种递归的复杂性将比原始递归复杂得多.

请注意,你不能在这里使用Master's定理,因为a < 1.

您可以开始展开递归.

最后一次求和变换,因为它是几何级数.因此,递归将在某个时间停止,您可以选择某个时间点.我选择它的时候T(1) = b.这发生在何时n/2^k = 1或n = 2^k意味着什么k = log n.

如果你将k在递归中替换它,你将得到最大的元素运行O(n),因此这是这个等式的运行时间.

错误的结束,正确的开始

其是T(n/2) + n = 0,它等于T(n) = - 2n,所以它是线性的.这对我来说是违反直觉的(这里是减号),但是凭借这个解决方案,我看到功能方程 的解决方案T(n)=T(n-1)+T(n/2)+n非常接近-2n - 2.

如果你将它插入等式中,你将看到n它只有1关闭.所以解决方案仍然存在O(n)

PS再一次,CS类的一个非常奇怪的递归.