求递归式T(n)=2T(n/3)+n/(logn)²的渐近复杂度，Master定理失效求解遇阻

嘿，我来帮你拆解这个问题——你遇到的卡壳点确实很典型，这个递归式刚好踩中了标准Master定理的盲区，不过我们可以通过迭代展开+渐近分析，或者变量替换来搞定它。

首先先明确为什么Master定理用不了：

• 这里递归参数 $a=2$，$b=3$，所以 $\log_b a = \log_3 2 \approx 0.63$
• 你的非递归项 $f(n) = \frac{n}{(\log n)^2}$，它比 $n^{\log_3 2}$ 增长快，但两者的比值 $\frac{f(n)}{n^{\log_3 2}} = \frac{n^{1 - \log_3 2}}{(\log n)^2} = \frac{n^{\log_3 (3/2)}}{(\log n)^2}$ 不是多项式级的增长（它趋向于无穷，但不是 $n^\varepsilon$ 这种纯多项式形式），因此不满足Master定理任何一种情况的严格条件。

接下来我们一步步处理你提到的求和式：

1. 迭代展开递归式 #

先把递归式展开到终止条件（当 $n/3^i$ 降到常数级别时，$T(n/3^i) = \Theta(1)$）：

T(n) = n/(log n)² + 2*(n/3)/(log(n/3))² + 2²*(n/3²)/(log(n/3²))² + ... + 2^k*Θ(1)

这里 $k \approx \log_3 n$，最后一项 $2^k*Θ(1) = Θ(n^{\log_3 2})$，它的增长速度远慢于前面的求和项（因为 $\frac{n}{(\log n)^2}$ 是 $\omega(n^\alpha)$ 对任意 $\alpha < 1$，而 $\log_3 2 < 1$），所以我们可以先专注于前面的求和部分：
$$S(n) = \sum_{i=0}^{k-1} \left(\frac{2}{3}\right)^i \cdot \frac{n}{(\log(n/3^i))²}$$

2. 简化求和的渐近行为 #

利用对数性质 $\log(n/3^i) = \log n - i\log 3$：

• 当 $n$ 很大时，对于大部分 $i$（$i \ll \log_3 n$），$i\log 3 \ll \log n$，所以 $\log(n/3^i) \approx \log n$，对应的项近似为 $\left(\frac{2}{3}\right)^i \cdot \frac{n}{(\log n)^2}$
• 这部分是首项为 $\frac{n}{(\log n)^2}$、公比为 $\frac{2}{3}$ 的等比数列，求和结果为：
  $$\frac{n}{(\log n)^2} \cdot \frac{1 - (2/3)^k}{1 - 2/3} = 3 \cdot \frac{n}{(\log n)^2} \cdot (1 - (2/3)^k)$$
• 当 $n \to \infty$ 时，$(2/3)^k = n^{\log_3(2/3)} = n^{-\log_3(3/2)} \approx n^{-0.37} \to 0$，所以这部分和的渐近阶是 $\Theta\left(\frac{n}{(\log n)^2}\right)$

3. 验证边缘项的影响 #

对于接近 $k$ 的 $i$（比如 $i = k - m$，$m$ 是小常数），$\log(n/3^i) = \log(3^m) = m\log3$，对应的项为：
$$\left(\frac{2}{3}\right)^{k-m} \cdot \frac{n}{(m\log3)^2}$$
代入 $n=3^k$ 后，这部分项的总和是 $\Theta(n^{\log_3 2})$，远小于 $\Theta\left(\frac{n}{(\log n)^2}\right)$，因此对整体渐近阶没有影响。

4. 变量替换法验证 #

我们也可以用变量替换来交叉验证：令 $n=3^m$（即 $m=\log_3 n$），递归式变为：
$$T(3^m) = 2T(3^{m-1}) + \frac{3^m}{m²}$$
令 $S(m)=T(3^{m)$，则递推式变为线性非齐次形式：$S(m)=2S(m-1)+\frac{3}m}{m²}$

它的特解可以通过求和得到：
$$S_p(m) = \sum_{i=0}^m 2^{m-i} \cdot \frac{3^i}{i²} = 2^m \sum_{i=0}^m \left(\frac{3}{2}\right)^i \cdot \frac{1}{i²}$$
这个求和的主导项是 $i=m$ 时的项：$2^m \cdot \left(\frac{3}{2}\right)^m \cdot \frac{1}{m²} = \frac{3^m}{m²}$，前面的项相对于它可以忽略（因为 $\left(\frac{3}{2}\right)^i$ 是指数增长，分母 $i²$ 是多项式级），所以 $S_p(m)=\Theta\left(\frac{3^m}{m²}\right)$，即 $T(n)=\Theta\left(\frac{n}{(\log_3 n)^2}\right)=\Theta\left(\frac{n}{(\log n)^2}\right)$（对数的底数不影响渐近阶）。

最终结论 #

这个递归式的解是：
$$T(n) = \Theta\left(\frac{n}{(\log n)^2}\right)$$

内容的提问来源于stack exchange，提问作者D.Kapoulas