求解含floor函数的递归算法的时间复杂度Big-Θ

数据老陈

2026-10-1

首先给出结论：你分析的递归算法时间复杂度为Θ(n)，以下是你提出的两个问题的具体解答：

我们分析的算法代码如下：

Recursion(n):
   while n > 1:
      n = floor(n/2)
      Recursion(n)

首先我们定义T(n)为输入规模为n时算法执行的操作总次数，T(n)天然满足单调不减属性：输入规模越大，执行的操作次数不会更少。
对于任意正整数n，显然有不等式：

n/2 - 1/2 ≤ ⌊n/2⌋ ≤ n/2

结合T(n)的单调不减属性，可得：

T(n/2 - 1/2) ≤ T(⌊n/2⌋) ≤ T(n/2)

在渐近复杂度分析中，规模差不超过1的输入对应的函数值，阶完全相同，因此T(⌊n/2⌋)和T(n/2)的渐近阶是等价的，后续分析可以直接用n/2代替⌊n/2⌋，floor操作不会影响最终的复杂度结论。

我们用数学归纳法完成证明：

基例验证
当n=1时，递归直接返回，T(1)=1，显然满足T(1) ≥ 1/2 *1；
当n=2时，进入while循环，n变为1后调用Recursion(1)，总操作次数T(2)=2，满足T(2)≥1/2 *2。
归纳假设
假设对于所有整数k <n，都有T(k) ≥ c*k，其中c=1/2为正的常数。
归纳推导
对于规模为n的输入，算法的while循环会迭代⌊log₂n⌋次，每次迭代调用Recursion(⌊n/2^i⌋)（i从1到⌊log₂n⌋），因此递推式可写为：
```
T(n) = 1 + Σ_{i=1}^{⌊log₂n⌋} T(⌊n/2^i⌋)
```
代入归纳假设可得：
```
T(n) ≥ 1 + Σ_{i=1}^{⌊log₂n⌋} (⌊n/2^i⌋)/2
     ≥ 1 + Σ_{i=1}^{⌊log₂n⌋} (n/2^i - 1)/2
```
计算求和项：
- 正项和Σ_{i=1}^∞ n/(2^{i+1}) = n/2
- 负项和最多为Σ_{i=1}^{⌊log₂n⌋} 1/2 = (log₂n)/2
因此可得：
```
T(n) ≥ 1 + n/2 - (log₂n)/2
```
当n≥2时，1 - (log₂n)/2 ≥0，因此T(n)≥n/2，归纳成立。
由此可得存在正的常数c=1/2，当n足够大时T(n)≥c*n，即T(n)∈Ω(n)。