求解递归关系式T(n) = T(n - ⌊log(n)⌋)+cn的闭合形式与时间复杂度

先来说说这个递归的背景哈——你是从一个特殊快排场景里推导出来的：当输入是指数增长的数组（比如$[2,4,8,...,2^n]$），每次选中位数当 pivot，能在$O(1)$时间找到，这时候最大的子数组大小大概是$n - \lfloor \log n \rfloor$，于是得到了这个递归（后来你补充说其实应该还有$T(\lfloor \log n \rfloor)$项，但先重点分析你最初提出的这个递归~）

我们先来拆解这个递归的时间复杂度，核心是看递归深度和每一层的计算代价：

步骤1：估算递归深度 #

递归每一步，问题规模$n$会减少$\lfloor \log n \rfloor$，直到$n$小到某个常数（比如$n ≤ 1$时$T(n)$为常数）。我们需要计算从$n$降到常数$k$需要多少步：

当$n$很大时，$\log n$的变化非常缓慢，我们可以用积分来近似深度$d$：深度满足$\int_{k}^{n} \frac{1}{\log x} dx \approx d$。这个积分是对数积分$\text{li}(n)$，而当$n \to \infty$时，$\text{li}(n) \sim \frac{n}{\log n}$（渐近等价），所以递归深度$d = \Theta\left( \frac{n}{\log n} \right)$。

步骤2：计算总时间代价 #

每一层的计算代价是$c \cdot n_i$，其中$n_i$是第$i$层的问题规模。总代价$T(n) = c \cdot \sum_{i=0}^{d-1} n_i$。

当$n$很大时，$\log(n - \log n) \approx \log n$（因为$\log(n - \log n) = \log n + \log\left(1 - \frac{\log n}{n}\right) \approx \log n$），所以每一步的规模近似为$n_i \approx n - i \cdot \log n$。代入求和式：
$$
\sum_{i=0}^{d-1} n_i \approx \sum_{i=0}^{d-1} (n - i \cdot \log n) = d \cdot n - \log n \cdot \frac{d(d-1)}{2}
$$

把$d \sim \frac{n}{\log n}$代入：

• 第一项$d \cdot n \sim \frac{n}{\log n} \cdot n = \frac{n^2}{\log n}$
• 第二项$\log n \cdot \frac{d^2}{2} \sim \log n \cdot \frac{n^2}{2 \log^2 n} = \frac{n^2}{2 \log n}$

两项相减后，求和结果约为$\frac{n^2}{2 \log n}$，因此$T(n) = \Theta\left( \frac{n^2}{\log n} \right)$。

补充：加入$T(\lfloor \log n \rfloor)$项的影响 #

你后来提到递归里应该还有$T(\lfloor \log n \rfloor)$项，其实这个项的时间代价完全可以忽略：$T(\log n)$的规模很小，它的递归深度是$\Theta\left( \frac{\log n}{\log \log n} \right)$，总代价是$\Theta\left( \frac{(\log n)^2}{\log \log n} \right)$，和$\Theta\left( \frac{n^2}{\log n} \right)$相比是高阶无穷小，所以不改变最终的渐近复杂度。

关于闭合形式 #

这类递归一般没有简洁的数学闭合形式，在算法分析中，我们更关注渐近复杂度——毕竟它已经能准确描述算法在大规模输入下的性能表现了。

回到你最初的快排场景：这个结果也符合直觉，因为每次只把最大的子数组缩小$\log n$的规模，相当于每次只处理掉很小一部分元素，所以总时间比普通快排的$O(n \log n)$要高，但比最坏情况的$O(n^2)$要低，是介于两者之间的$\Theta\left( \frac{n^2}{\log n} \right)$。

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