Question

已知T(n)=2T(n/2)+n，T（1）=1，求T(n)

Answer 1

算法。

复杂度（计算机复杂性理论）

计算复杂性理论（Computational complexity theory）是计算理论的一部分，研究计算问题时所需的资源，比如时间和空间，以及如何尽可能的节省这些资源。

计算复杂性理论所研究的资源中最常见的是时间复杂度（要通过多少步才能解决问题）和空间复杂度（在解决问题时需要多少内存）。

Answer 2

由S(n+1)=2S(n)+n+5得S(n+1)+(n+1)+6=2[S(n)+n+6]令b(n)=S(n)+n+6，则b(n+1)=S(n+1)+(n+1)+6且b(n+1)=2b(n)从而得b(n)=2^(n-1)b(1)而b(1)=S(1)+1+6=a(1)+7=5+7=12所以b(n)=(2^n)*6即S(n)+n+6=(2^n)*6得S(n)=(2^n)*6-n-6可得a(n)=S(n)-S(n-1)=(2^n)*6-n-6-{[2^(n-1)]*6-(n-1)-6}=(2^n)*3-1 (n≥2)而a(1)=5满足上式，所以数列{a(n)}的通项公式为：a(n)=(2^n)*3-1由f(x)=a(1)x+a(2)x^2+……+a(n)x^n则f‘(x)=a(1)+2a(2)x+……+na(n)x^(n-1)从而得f‘(1)=a(1)+2a(2)+……+na(n)将a(n)=(2^n)*3-1代入上式得f'(1)=(2^1)*3-1+2[(2^2)*3-1]+……+n[(2^n)*3-1]=3[2^1+2(2^2)+……+n(2^n)]-(1+2+……+n)=3T(n)-n(n+1)/2其中T(n)=2^1+2*(2^2)+……+n(2^n)由2T(n)=2^2+2(2^3)+……+n*2^(n+1)用上式减下式，可得-T(n)=2^1+2^2+……+2^(n-1)-n*2^(n+1)化简得T(n)=n*2^(n+1)-(2^n-2)带入到f'(1)中得到：f'(1)=3[n*2^(n+1)-(2^n-2)]-n(n+1)/2=3(2n-1)*2^n-n(n+1)/2+6