数组最大k步跳跃得分暴力解法的时空复杂度分析咨询

题目说明 #

计算数组中每次最多跳跃k步时可获得的最大得分路径，题目示例：

• 输入：nums = [1,-1,-2,4,-7,3]，k = 2
• 输出：7
• 解释：选择跳跃步形成子序列[1,-1,4,3]，对应路径和为7。

待分析的暴力递归实现 #

public int maxResult(int[] nums, int k) {
    return maxResult(nums, k, nums.length - 1);
}

private int maxResult(int[] nums, int k, int index) {
    if (index == 0)
        return nums[0];
    int max = Integer.MIN_VALUE;
    int start = index - k < 0 ? 0 : index - k;
    
    for ( int i = start; i < index; i++ ) {
        int res = maxResult(nums, k, i);
        System.out.println(i);
        max = Math.max(res, max);
    }
    return max + nums[index];
}

原有复杂度猜想 #

• 猜想1：每个元素位置会触发k次函数调用，因此时间、空间复杂度为O(k^n)，其中n为数组长度。
• 猜想2：首个元素最多触发1次调用，第二个元素最多触发2次调用（当k>i时），调用次数逐次累加直到k次，后续位置均触发k次调用，对应求和式计算得复杂度为O(k²)。

正确复杂度结论与推导 #

• 时间复杂度：O(k^n)（指数级）
  猜想1的结论是正确的，猜想2的核心错误是默认每个位置的计算结果会被复用，相当于给代码额外加了记忆化缓存，完全不符合当前无缓存递归的实际执行逻辑。
  我们可以直接通过递归调用关系推导：定义T(i)为计算位置i的最大得分总共产生的函数调用次数：

  1. 边界条件：位置0直接返回结果，仅产生1次调用，即T(0) = 1
  2. 递推关系：对于任意位置i>0，当前函数本身占1次调用，还需要遍历所有前序k步可达的位置j，对每个j都完整发起递归调用——由于没有缓存，每次调用j都会重新执行j位置的全部递归逻辑，不会复用之前的计算结果，因此T(i) = 1 + sum_{j=max(0, i-k)}^{i-1} T(j)
     以题目中k=2的场景计算前几个位置的调用量，就能直观看到指数增长趋势：
  • T(0) = 1
  • T(1) = 1 + T(0) = 2
  • T(2) = 1 + T(0) + T(1) = 4
  • T(3) = 1 + T(1) + T(2) = 7
  • T(4) = 1 + T(2) + T(3) = 12
  • T(5) = 1 + T(3) + T(4) = 20
    当i大于k之后，每个位置的调用量近似等于前k个位置的调用量之和，每个递归步骤最多分出k个独立分支，整体时间上界为O(k^n)。

• 空间复杂度：O(n)
  空间开销全部来自递归调用栈，递归最深的路径是从数组末尾逐格跳到位置0，栈深度为n；代码中没有申请其他随n、k增长的额外内存空间，因此空间复杂度为线性的O(n)。

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