含两次递归调用的递归函数时间复杂度疑问：为何结果为O(n)？

首先看对应的递归函数代码：

void foo(int n){ 
    if(n>1){ 
        foo(n/2); 
        foo(n/2);
    }
}

递归式的定义 #

该函数的时间复杂度递归式为：
T(n) = 2T(n/2) + Θ(1)
其中：

• 2T(n/2) 表示调用两个规模为n/2的子问题
• Θ(1) 表示当前函数中判断、函数调用等常数时间开销

重复代入法的完整推导过程 #

你已经完成了前几步代入，这里补全关键步骤并解释：

1. 第k次代入后，递归式会展开为：
   T(n) = 2ᵏT(n/2ᵏ) + Θ(1)×(2⁰ + 2¹ + 2² + ... + 2ᵏ⁻¹)
   这里的求和项是每次代入后累加的常数开销，是一个首项为1、公比为2的等比数列。

2. 确定递归终止条件（k的取值）：
   当递归到base case时，n/2ᵏ = 1（假设n是2的幂，不影响渐近复杂度结论），解得2ᵏ = n，即k = log₂n。

3. 代入k的值计算两项：

   • 第一项：2ᵏT(n/2ᵏ) = n×T(1)，而T(1)是base case的时间（n≤1时直接返回，开销为常数），所以第一项等价于nΘ(1)。
   • 第二项：等比数列求和结果为2ᵏ - 1，代入2ᵏ = n后得到n - 1，乘以Θ(1)就是(n-1)Θ(1)。

4. 合并结果并简化：
   把两项相加得到：
   T(n) = nΘ(1) + (n-1)Θ(1) = (2n - 1)Θ(1)
   在渐近复杂度分析中，常数系数和低阶项可以忽略，因此最终时间复杂度为O(n)。

直观理解 #

从递归树的角度看：

• 递归树共有log₂n层（从根到base case）
• 第i层有2ⁱ⁻¹个节点，每个节点的开销是Θ(1)，因此每层总开销为2ⁱ⁻¹×Θ(1)
• 所有层的总开销求和就是Θ(1)×(1 + 2 + 4 + ... + n/2)，这个和等于Θ(n)，和推导结果一致。

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