最小跳转数组递归时间复杂度应为O（n^n）或O（n！）

Question

我在GeekforGeekshttps://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/中检查“到达终点的最小跳跃次数”问题。我对这里提到的时间复杂度感到困惑，它是O（n^n）。

// Returns minimum number of
// jumps to reach arr[h] from arr[l]
static int minJumps(int arr[], int l, int h)
{
    // Base case: when source
    // and destination are same
    if (h == l)
        return 0;
 
    // When nothing is reachable
    // from the given source
    if (arr[l] == 0)
        return Integer.MAX_VALUE;
 
    // Traverse through all the points
    // reachable from arr[l]. Recursively
    // get the minimum number of jumps
    // needed to reach arr[h] from these
    // reachable points.
    int min = Integer.MAX_VALUE;
    for (int i = l + 1; i <= h
                        && i <= l + arr[l];
         i++) {
        int jumps = minJumps(arr, i, h);
        if (jumps != Integer.MAX_VALUE && jumps + 1 < min)
            min = jumps + 1;
    }
    return min;
}

如果我看到上面的代码块，minJumps（arr，I，h）递归调用是从I=l1调用的。所以在每个递归步骤中，l（起始位置）都会增加1。时间复杂度的计算方法如下。

T(N) = (n-1)*(n-2)*(n-3)...*1
     = (n-1)!
 

我不明白为什么时间复杂度是O（n^n）。在其他地方，我也看到这个递归解的时间复杂度被称为O（n^n），没有适当的解释。请给我一个简单的解释

Answer 1

我可以看到递归关系为T（n）=T（n-1）T（n-2）T（n-3）T（n-4）。。。T（0），因为循环是从l到h（暂时忽略if条件）。因此，对于一个区间[l，h]在最坏的情况下，该区间中的每个值都将被调用，即minJumps（l1，h），minJumps（l2，h）。。。minJumps（h，h），可以注意到上面的递归关系在这里成立。

现在，解决这个关系，我们可以把它写成T（n）=T（n-1）T（n-1）asT（n-1）=T（n-2）T（n-3）T（n-4）。。。T（0）。因此T（n）=2*T（n-1）归结为O（2^n）。

上述算法的时间复杂度应为O（2^n）。