Question

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

Answer 1

记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)