递推关系：求解T(n) = 25T(n/5) + ((n log 5) / (log n))^2

Question

T(n) = 25T(n/5) + ((n log 5) / (log n))^2

我是递归关系的新手，一直在解决上述问题，想寻求一些方向！

我不认为我能够在这里应用主定理，这导致我使用伸缩级数，在那里我能够将关系（通过除以 n^2 log^2 5）简化为 T(n) 的形式= T(1)/1 + (1/2)^2 + (1/4)^2 + ... + (1/logn)^2。之后我无法进一步简化。

感谢任何建议！

Answer 1

提示。

在

n = 5^m

之后可以重铸为

r[m] = 25*r[m-1]+(5^m/m)^2

现在这是线性的，可以得到解

r[n] = rh[m] + rp[m]

齐次有解

rh[m] = 5^(2*m)c0

为了获得一个特定的解决方案，我们继续考虑

rp[m] = 5^(2*m)c0[m]

替换后

5^(2*m)c0[m] =  5^2*5^(2*(m-1))c0[m-1] + (5^(2*m)/m)^2

或简化

c0[m] = c0[m-1] + 1/m^2

解决方案

c0[m] = pi^2/6 - PolyGamma[1,1,m]

然后

rp[m] = 5^(2*m)*(pi^2/6 - PolyGamma[1,1,m])

最后

r[m] = (pi^2/6 - PolyGamma[1,1,m] + c0)*5^(2*m)

获得

T[n]

所需的后退步骤留给读者。