如何用递归树法计算T(n)=T(n-sqrt(n))+n²的时间复杂度

数据老陈

2026-6-13

递推式T(n) = T(n - √n) + n²的时间复杂度分析

一、递归树高度的数学证明

递归树高度指从初始规模n递归到基准情况（如T(c)=O(1)，c为常数）的步数k。

我们通过微分方程近似推导高度：
设第i步的问题规模为$n_i$，递推关系为$n_i = n_{i-1} - \sqrt{n_{i-1}}$，初始$n_0 = n$。当n足够大时，将离散递推近似为连续微分关系：$\frac{dn}{dk} \approx -\sqrt{n}$。

分离变量并积分（c为递归终止的常数规模）：
$$\int_{n}^{c} \frac{dn}{\sqrt{n}} = -\int_{0}^{k} dk$$
计算得：
$$2(\sqrt{c} - \sqrt{n}) = -k$$
整理后$k \approx 2(\sqrt{n} - \sqrt{c})$，显然$k = O(\sqrt{n})$，即递归树高度为Θ(√n)。

为验证严谨性，做变量替换$m_i = \sqrt{n_i}$，则$n_i = m_i^2$，代入递推式得：
$$m_i^2 = m_{i-1}^2 - m_{i-1}$$
当$m_i$很大时，泰勒展开近似得$m_i \approx m_{i-1} - \frac{1}{2}$，初始$m_0 = \sqrt{n}$，因此$m_k \approx \sqrt{n} - \frac{k}{2}$。当$m_k$降到常数时，$k \approx 2\sqrt{n}$，进一步确认高度为Θ(√n)。

二、整体时间复杂度推导

递归树每一层代价为当前规模的平方，总时间复杂度为所有层代价之和加基准常数项：
$$T(n) = \sum_{i=0}^{k-1} n_i^2 + O(1)$$

利用$n_i \approx (\sqrt{n} - \frac{i}{2})^2 = n - i\sqrt{n} + \frac{i^2}{4}$，将求和近似为积分（n很大时，求和与积分误差可忽略）：
$$\sum_{i=0}^{k-1} n_i^2 \approx \int_{0}^{2\sqrt{n}} (\sqrt{n} - \frac{t}{2})^4 dt$$

令$u = \sqrt{n} - \frac{t}{2}$，$du = -\frac{dt}{2}$，转换积分上下限后计算：
$$\int_{0}^{2\sqrt{n}} (\sqrt{n} - \frac{t}{2})^4 dt = 2\int_{0}^{\sqrt{n}} u^4 du = \frac{2}{5}n^{5/2}$$

因此，总时间复杂度为Θ(n^{5/2})。