递归关系式求解求助：T(n)=25T(n/5)+((n log5)/(logn))²

为什么主定理不适用？ #

这里 $a=25$，$b=5$，所以 $\log_b a = \log_5 25 = 2$。主定理要求 $f(n)$ 与 $n^{\log_b a}$ 满足多项式级的大小关系：

• $f(n) = \left(\frac{n \log 5}{\log n}\right)^2 = n^2 \cdot \frac{\log^2 5}{\log^2 n}$，它比 $n^2$ 小，但不是多项式级的小（$\frac{1}{\log^2 n}$ 不是多项式函数），因此主定理的三种情况都不匹配，确实无法直接应用。

正确的变量替换与 telescoping 展开 #

令 $S(n) = \frac{T(n)}{n^2}$，将原递归式两边除以 $n^2$：
$$
\begin{align*}
\frac{T(n)}{n^2} &= \frac{25T(n/5)}{n^2} + \frac{\left(\frac{n \log 5}{\log n}\right)^2}{n2} \
S(n) &= \frac{T(n/5)}{(n/5)^2} + \frac{\log^2 5}{\log^2 n} \
S(n) &= S(n/5) + \frac{\log^2 5}{\log^2 n}
\end{align*}
$$

假设 $n = 5^k$（$k$ 为正整数），则 $\log n = \log 5^k = k \log 5$，代入上式得：
$$
S(5^k) = S(5^{k-1}) + \frac{\log^2 5}{(k \log 5)^2} = S(5^{k-1}) + \frac{1}{k^2}
$$

展开 telescoping 序列：
$$
S(5^k) = S(1) + \sum_{i=1}^k \frac{1}{i^2}
$$

因为 $S(1) = \frac{T(1)}{1^2} = T(1)$，且 $k = \log_5 n$，所以代回 $T(n)$：
$$
T(n) = n^2 \left( T(1) + \sum_{i=1}^{\log_5 n} \frac{1}{i^2} \right)
$$

渐近行为分析 #

我们知道无穷级数 $\sum_{i=1}^\infty \frac{1}{i^2} = \frac{\pi^2}{6} \approx 1.6449$，这是一个收敛的常数。因此无论 $n$ 多大，$\sum_{i=1}^{\log_5 n} \frac{1}{i^2}$ 始终小于这个常数，所以：
$$
T(n) = \Theta(n^2)
$$

非5的幂的情况 #

如果 $n$ 不是5的整数次幂，可以通过递归树或代入法证明，$T(n)$ 的渐近复杂度仍然是 $\Theta(n^2)$——因为递归过程中每次的余项求和始终被收敛级数的上界限制，不会影响主导项 $n^2$。

内容的提问来源于stack exchange，提问作者Goonturr