如何计算给定递归C语言函数f(n)的时间复杂度

首先给出函数源码：

void f(int n) 
{
 doOh(n);
 if(n<1) return;
 for(int i=0; i<2; i++)
 {
   f(n/2);
 }
}

步骤1：推导递归递推式 #

先分析单次调用f(n)的执行开销：

• 每次调用首先执行doOh(n)，已知它的时间复杂度是O(n)
• 若n < 1直接返回，终止逻辑的开销为O(1)
• 若n >= 1，会循环执行2次f(n/2)

由此可以得到时间复杂度的递推关系：

T(n) = 2 * T(n/2) + O(n) （n >= 1时）
T(n) = O(1) （n < 1时）

步骤2：递推展开计算量级 #

我们把递推式逐层展开：

• 第一层：T(n) = 2T(n/2) + n
• 第二层：把T(n/2)代入，得T(n) = 2*(2T(n/4) + n/2) + n = 4T(n/4) + 2n
• 第三层：把T(n/4)代入，得T(n) = 4*(2T(n/8) + n/4) + 2n = 8T(n/8) + 3n

以此类推，展开到第k层时的公式为：
T(n) = 2^k * T(n/2^k) + k * n

步骤3：代入终止条件得到最终结果 #

递归终止的条件是n/2^k < 1，即2^k > n，可得k ≈ log₂n，把k代入上面的展开式：

• 第一项2^k * T(n/2^k)中，2^{k约等于n，T(n/2}k)是O(1)，因此这一项的量级是O(n)
• 第二项k * n约等于n * log₂n，量级是O(n log n)

取最高阶的项，最终f(n)的时间复杂度为O(n log n)。

补充：主定理快速验证 #

对于形式为T(n) = aT(n/b) + f(n)的递归递推式，可以用主定理直接计算：
本题中a=2，b=2，f(n)=O(n)，计算得n^log_b a = n^log₂2 = n，f(n)和这个值是同阶量级，符合主定理第二种情况，直接得到T(n)=O(n log n)，和展开计算的结果一致。

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