带缓存递归函数的时间复杂度及严谨证明方法探讨

先看你给出的示例代码：

@cache
def fn(i, j):
  if i > j:
    return 0
  
  for k in range(i, j + 1):
    fn(i, k - 1)
    fn(k + 1, j)

一、示例函数的时间复杂度严谨证明 #

带@cache的递归本质是记忆化搜索，核心是每个(i,j)组合的状态只会被实际执行一次，后续调用直接返回缓存值，所以总时间等于所有唯一状态的实际执行开销之和。

1. 定义状态与统计数量 #

用len = j - i + 1表示区间长度：

• 当len=0（即i>j），是基础情况，直接返回0，时间开销O(1)，这类状态有n+1个（i从0到n，j=i-1）。
• 当len≥1，区间长度为len的(i,j)组合共有n - len + 1个（比如len=1时，i可以是0到n，共n+1个；len=2时i是0到n-1，共n个，以此类推）。

2. 计算每个状态的实际执行开销 #

对于每个长度为len≥1的状态fn(i,j)，实际执行的开销包括：

• 基础判断的O(1)时间；
• 循环k从i到j，共len次迭代，每次迭代触发两个子调用——但子调用如果已经被缓存，只是O(1)的返回；如果是新状态，那它的开销会被单独统计在对应状态里。这里我们只需要统计当前状态自身的循环次数（每次迭代的操作是O(1)）。

3. 总开销求和 #

总循环开销是所有len≥1的状态的循环次数之和：

总循环次数 = Σ（len从1到n） [len * (n - len + 1)]

展开计算这个求和式：

• 拆成(n+1)*Σlen - Σlen²，其中Σlen从1到n是n(n+1)/2，Σlen²从1到n是n(n+1)(2n+1)/6
• 代入后化简得到：n(n+1)(n+2)/6，这是组合数C(n+2,3)，属于O(n³)量级。

再加上所有状态的基础判断开销（共(n+1)(n+2)/2个状态，O(n²)量级），相对于O(n³)可以忽略。所以总时间复杂度是O(n³)，和朴素分析结果一致，但这里通过统计每个唯一状态的实际执行开销，避免了重复计算缓存命中的调用，是严谨的证明。

二、带缓存递归时间复杂度的通用分析方法 #

1. 先锁定所有唯一状态 #

记忆化搜索的核心是“每个状态只执行一次”，第一步必须明确：

• 什么是递归的“状态”？就是能唯一确定递归分支的参数组合，比如示例中的(i,j)，子集问题中的当前位置+已选元素状态。
• 统计所有可能的唯一状态总数，记为S。

2. 计算单个状态的实际执行开销 #

对每个状态，只算它第一次被调用时的执行开销：

• 包括自身的基础判断、循环/分支操作等，这些是当前状态独有的开销；
• 子调用的开销别算在这里——如果子调用是新状态，它的开销会被单独统计；如果是缓存命中，只是O(1)的返回，这部分可以算在当前状态的开销里（毕竟是当前调用触发的查询）。

3. 求和得到总时间 #

总时间复杂度就是所有状态的实际执行开销之和 + O(S)（O(S)是所有缓存查询的总开销，每个状态最多被查询一次，每次O(1)）。

4. 避坑关键 #

• 别把“触发子调用”等同于“子调用实际执行”：带缓存时，大部分子调用都是命中缓存，只花O(1)，不是子调用的完整执行时间；
• 绝对不能重复计算：每个状态的实际执行只算一次，不管被触发多少次；
• 复杂递归可以用递推式：比如定义T(n)表示处理规模为n的问题的总时间，根据递归关系写递推方程，再用代入法、递归树法或主定理求解。

比如你提到的子集生成meth_2，错误分析把每次循环的n都算进去，但实际上每个状态的执行开销是O(1)，唯一状态数是O(2ⁿ)，所以总时间是O(2ⁿ)，而非O(n*2ⁿ)。

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