求下述递归函数的大O时间复杂度及推导方法

这个函数的时间复杂度是O(2ⁿ)，不是你推测的O(2^(n·logn))，具体推导过程如下：

1. 定义递归关系式 #

设T(n)表示调用function(n)的总时间复杂度：

• 基础情况：当n=0时，函数直接返回，所以T(0) = O(1)（常数时间）。
• 递归情况：当n>0时，函数会调用function(n-1)和function(n/2)，加上常数时间的条件判断，因此递归式为：

  T(n) = T(n-1) + T(n/2) + O(1)
  

2. 推导上界 #

观察递归式可以发现，当n≥2时，n/2 ≤ n-1，因此T(n/2) ≤ T(n-1)（递归函数的时间复杂度随输入增大而递增）。代入递归式可得：

T(n) ≤ T(n-1) + T(n-1) + O(1) = 2·T(n-1) + O(1)

这个简化后的递归式的解是O(2ⁿ)：每次递归调用的时间都是前一次的2倍加常数，展开后总时间为2ⁿ·T(0) + O(2ⁿ)，忽略低阶项后就是O(2ⁿ)。

3. 验证上界的紧致性 #

用数学归纳法证明T(n) = Θ(2ⁿ)（即上界和下界都是O(2ⁿ)）：

• 假设对于所有k < n，存在常数C使得T(k) ≤ C·2ᵏ。

• 代入递归式：

  T(n) = T(n-1) + T(n/2) + 1 ≤ C·2ⁿ⁻¹ + C·2^(n/2) + 1
  

  当n≥2时，2^(n/2) ≤ 2ⁿ⁻¹（因为n/2 ≤ n-1），因此C·2^(n/2) ≤ C·2ⁿ⁻¹，代入后：

  T(n) ≤ C·2ⁿ⁻¹ + C·2ⁿ⁻¹ + 1 = C·2ⁿ + 1
  

  只要取C≥1，当n足够大时，C·2ⁿ + 1 ≤ 2C·2ⁿ，即T(n) ≤ C'·2ⁿ，上界成立。

  对于下界，显然T(n) ≥ T(n-1)，而T(n-1)的增长速度至少是2ⁿ⁻¹（由递归式结构可知），因此T(n) = Ω(2ⁿ)。

4. 为什么你的推测不对 #

O(2^(n·logn))的增长速度远快于O(2ⁿ)，但实际上递归中function(n/2)的分支会快速收敛到0（对数级深度），而function(n-1)的分支是线性深度（从n递减到0），后者主导了整个递归的时间复杂度，因此整体增长速度是2ⁿ而非更高的量级。

内容的提问来源于stack exchange，提问作者itstommi