如何用生成函数求解递归方程f(n)=2f(n/2)+cn

Question

算法的东西不上这儿上哪里呀，同志

Answer 1

解：

令f(1)=c

f(2)=2c+2

f(4)=2(2c+2)+4 = 4c+8

f(8) = 2(4c+8)+8 = 8c+24

f(16) = 2(8c+24)+16 = 16c+64

f(2^k) = c*2^k + P(k)

考虑P(k)

P(0) = 0

P(1) = 2 *P(0) + 2

P(2) = 2*P(1)+4

p(n-2) = 2*P(n-3)+2^(n-2)

p(n-1) = 2*P(n-2)+2^(n-1)P(n) 

= 2* P(n-1) + 2^n = 2*2*P(n-2)+2*2^(n-1)+2^n 

= 4P(n-2)+2*2^n

= 4*2P(n-3)+4*2^(n-2)+2*2^n

归纳得到P(n) = 2^kP(n-k)+k*2^n = 2^nP(n-n)+n*2^n =n*2^n

所以P(n-1) = (n-1)2^(n-1)

2*P(n-1)+2^n = 2*(n-1)*2^(n-1) + 2^n=P(n) 得到验证

带回f(2^k)得到f(2^k) = c*2^k+k*2^k，对于任意常数c成立

扩展资料

性质：

1、 子问题须与原始问题为同样的事，且更为简单。

2、不能无限制地调用本身，须有个出口，化简为非递归状况处理。

3、由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

4、递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

Answer 2

记n = 2^k, f(n) = f(2^k) = h(k),
那么有h(k) = 2*h(k-1) + c*2^k
记 // sigama就是求和号，这里打不出来，只好这样写
// sigama[k=0,无穷]分别是求和号的下标和上标
G(x) = sigama[k=0,无穷] h(k)*x^k
2x*G(x) = sigama[k=0,无穷] 2*h(k)*x^(k+1)
G(x)-2*x*G(x) = (1-2x)*G(x)
= h(0) + sigama[k=0,无穷] (h(k+1) - 2*h(k))*x^(k+1)
= h(0) + c * sigama[k=0,无穷] 2^(k+1)*x^(k+1)
= h(0) + c * sigama[k=0,无穷] (2*x)^(k+1)
= h(0) + c * (2*x/(1-2*x))

故G(x) = h(0)/(1-2*x) + c * (2*x/(1-2*x)^2)
= h(0)/(1-2*x) + c * (1/(1-2*x)^2 - 1/(1-2*x))
= (h(0) - c) * 1/(1-2*x) + c * 1/(1-2*x)^2
= (h(0) - c) * sigama[k=0,无穷] (2*x)^k
+ c * sigama[k=0,无穷] (k+1)(2*x)^k
// 为了方便计算设f(1) = h(0) = 0, f(2) = h(1) = 2*c
// 其实不这样设也可以的，计算过程与下面类似
= (- c) * sigama[k=0,无穷] (2*x)^k
+ c * sigama[k=0,无穷] (k+1)(2*x)^k
= c * sigama[k=0,无穷] k * (2*x)^k
= sigama[k=0,无穷] c * k * (2*x)^k
= sigama[k=0,无穷] h(k)*x^k

所以h(k) = c * k * 2^k,
而n = 2^k
则f(n) = h(k) = c * k * 2^k = c * n * log2 n;
// log2 n 表示以2为底的对数
f(n) = O(n * log2 n)