如何计算并证明含三次递归调用函数的时间复杂度？

一、目标函数的时间复杂度证明 #

先定义递推式：设T(x)为调用fun(arr, x)的时间复杂度。

• 基例：当x ≤ 0时，函数仅执行返回arr[0]的常数操作，因此T(x) = O(1)。
• 递归情况：每次调用会触发3次递归调用（分别对应x-1、x-2、x-4），加上当前的赋值、比较等常数操作，因此递推式为：

  T(x) = T(x-1) + T(x-2) + T(x-4) + O(1)
  

接下来用数学归纳法证明T(x) = O(3^x)：

1. 基例验证：当x ≤ 0时，取足够大的常数C ≥ 1，有T(x) = O(1) ≤ C·3^x（因为3^0=1，常数操作必然小于等于C·1）。
2. 归纳假设：假设对于所有k < x，均满足T(k) ≤ C·3^k。
3. 归纳推导：
   将递推式代入假设：

   T(x) ≤ C·3^{x-1} + C·3^{x-2} + C·3^{x-4} + D
   

   其中D是常数操作的上界。提取公因子C·3^{x-4}：

   T(x) ≤ C·3^{x-4}(3^3 + 3^2 + 1) + D = C·3^{x-4}·37 + D
   

   由于37 < 81 = 3^4，因此C·3^{x-4}·37 < C·3^{x-4}·3^4 = C·3^x。只要取C足够大，使得D ≤ C·3^x - C·3^{x-4}·37对所有x ≥ 1成立，就能得到T(x) ≤ C·3^x，即T(x) = O(3^x)。

注：实际上该函数的时间复杂度可以更紧凑（比如小于3^x），但上述证明已满足你对O(3^x)的求证需求。

二、多递归调用复杂度分析的学习资源推荐 #

• 《算法导论》（CLRS）：书中递归式章节系统讲解了代入法、递归树法，也涵盖主定理的扩展场景。主定理并非仅适用于两次调用的算法，只是标准形式针对分治类的“a个子问题+每个子问题规模n/b”场景，而多分支递归更适合用代入法或递归树推导。
• 《数据结构与算法分析：C语言描述》：对递归复杂度的讲解直观易懂，包含大量多递归调用的实例，适合入门建立直观认知。
• 高校算法课程讲义：多数名校的算法公开课讲义中，会专门针对非分治类的多分支递归，用归纳法、递归树一步步拆解推导过程，能帮你掌握通用的分析方法。

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