数组最小跳跃次数递归解法时间复杂度O(N!)与O(n^n)差异疑问

• 你的推导逻辑本身没有错误，得到的O(N!)是该解法更精确的紧上界。你推导时结合了问题的核心约束：跳跃只能向前进行，不能回退也不能越过数组边界，因此下标为i的位置最多只有N-1-i种合法步长选择，把每层递归的最大分支数相乘，确实可以得到(N-1)*(N-2)*...*1=(N-1)!，对应大O记法为O(N!)。
• Geeks for Geeks给出的O(n^n)是更宽松的通用上界，推导时没有额外利用前向跳跃的约束，默认每个递归节点最多有n种分支选择，同时递归深度最多为n（每次至少跳1步，最多跳n次必然触达数组边界），直接相乘就得到了n^n的上界。这个上界精度更低，但逻辑上完全成立。
• 两者本质只是上界的严格程度不同，没有对错之分。工程场景分析暴力递归复杂度时，往往会优先选用更易推导的宽松上界，而且两种上界都属于超指数复杂度范畴，都能准确说明该暴力解法效率极低，无法应对稍大的输入规模。

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