求解递推式T(n)=T(n-3)+1/log n时的求和项近似方法咨询

嘿，你已经把递推式展开到k步的形式了，这一步做得很扎实！接下来我们可以用积分近似法来处理这个求和项——这是分析这类包含对数倒数的离散求和时最常用的技巧之一，咱们一步步来拆解：

首先先明确k的取值：当递推到基准情况时，n-3k会是一个常数（比如假设基准情况T(c)=Θ(1)，c是某个固定常数），所以k≈n/3，此时求和项覆盖的是从log n到log c的一系列倒数项，每两项之间的自变量间隔是3。

用积分近似离散求和 #

我们的求和项是：
$$S = \sum_{i=0}^{k-1}\frac{1}{\log{(n-3i)}}$$
可以把它变形为：
$$S = \frac{1}{3} \sum_{i=0}^{k-1}\frac{3}{\log{(n-3i)}}$$
这里的每一项$\frac{3}{\log{(n-3i)}}$，可以看作是函数$f(x)=\frac{1}{\log x}$在区间$[n-3(i+1), n-3i]$上的矩形面积（宽度为3，高度为区间左端点的函数值）。因为$f(x)=\frac{1}{\log x}$是单调递减函数（对数函数递增，倒数自然递减），所以离散求和的结果和$f(x)$在区间$[c, n]$上的积分结果是同阶的——也就是说：
$$\sum_{i=0}^{k-1}\frac{3}{\log{(n-3i)}} \sim \int_{c}^{n} \frac{1}{\log x} dx$$

积分的渐近近似 #

这个积分$\int \frac{1}{\log x} dx$是数学里的对数积分函数，记作$\text{li}(x)$。我们可以用分部积分法推导它的渐近行为：
令$u=\frac{1}{\log x}$，$dv=dx$，则$du=-\frac{1}{x(\log x)^2}dx$，$v=x$，代入分部积分公式得：
$$\int \frac{1}{\log x} dx = \frac{x}{\log x} + \int \frac{x}{x(\log x)^2} dx = \frac{x}{\log x} + \int \frac{1}{(\log x)^2} dx$$
当$x$趋向于无穷大时，后面的积分项$\int \frac{1}{(\log x)^2} dx$是比$\frac{x}{\log x}$更低阶的项（再次分部积分就能看到它的量级是$\frac{x}{(\log x)^2}$，增长远慢于$\frac{x}{\log x}$），所以对数积分的渐近近似是：
$$\text{li}(x) \sim \frac{x}{\log x} \quad (x \to \infty)$$

最终结论 #

把这个结果代入我们的求和项：
$$S \sim \frac{1}{3} \cdot \frac{n}{\log n}$$
也就是$S = \Theta\left(\frac{n}{\log n}\right)$。再加上基准项$T(n-3k)=\Theta(1)$（常数阶），整个递推式的解就是：
$$T(n) = \Theta\left(\frac{n}{\log n}\right)$$

如果需要更严谨的证明，还可以用积分上下界来约束求和：因为$f(x)$递减，所以有
$$\int_{c}^{n} \frac{1}{\log x} dx \leq 3S \leq \int_{c-3}^{n+3} \frac{1}{\log x} dx$$
左右两边的积分都是$\Theta\left(\frac{n}{\log n}\right)$，所以同样能得出$S=\Theta\left(\frac{n}{\log n}\right)$的结论。

备注：内容来源于stack exchange，提问作者lKaladinl