最小跳跃数组递归解法时间复杂度应为O(n^n)还是O(n!)

你的推导疏漏说明 #

你推导的O(n!)是建立在「每个起始位置l只会被递归调用1次」的前提上，但这个朴素递归没有加入记忆化缓存，同一个l会被多条不同的上层递归路径重复调用，这个前提不成立，所以阶乘的推导结果是实际调用次数的下界，不是上界。

为什么标注为O(nⁿ) #

这个是算法复杂度标注里常见的「宽松上界」写法，逻辑如下：

• 最坏情况是数组每个位置l的值都足够大，可以跳到它之后的所有位置，比如数组为[n-1, n-1, n-1, ..., n-1]
• 每次递归调用对应1个l值，取值范围总共有n种可能（0到n-1）
• 每个递归调用最多会发起n次新的递归调用，递归深度最多为n层
• 所以总的调用次数上界可以直接用n^n表示，这个上界虽然不够紧，但完全符合大O表示法的定义（大O只要求给出增长上界，不要求是最紧的上界）

两者的关系 #

你推导的O(n!)其实是比O(n^n)更紧的上界：我们都知道n! = 1*2*3*...*n，而n^n = n*n*n*...*n，显然n! < n^n，所以O(n!)是比O(n^n)更精确的复杂度表述。很多资料会直接标注O(n^n)，主要是为了降低解释成本，不需要额外说明阶乘级复杂度的推导逻辑，普通开发者也能快速理解这是一个非常高的指数级复杂度。

小例子验证 #

以n=3、数组[2,1,0]为例：
总递归调用路径如下：

1. minJumps(arr, 0, 2) → 调用i=1、i=2
   2. minJumps(arr, 1, 2) → 调用i=2
   3. minJumps(arr, 2, 2) → 返回0
   4. minJumps(arr, 2, 2) → 返回0
   总调用次数为4次：

• 你的阶乘推导值是(3-1)! = 2，小于实际调用次数
• n^n = 27，远大于实际调用次数，符合上界定义

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