最小跳转数组递归时间复杂度应为 O(n^n) 或 O(n!)

Question

我在 GeekforGeeks https://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;
}

如果我看到上面的代码块，则表明正在从 i=l+1 调用 minJumps(arr, i, h) 递归调用。所以在每个递归步骤中，l(start position) 都会增加 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(l+1, h), minJumps(l+2, h) ... minJumps(h, h)，并且可以注意到上面的递归关系在这里成立。

现在，求解关系，我们可以把它写成T(n) = T(n-1) + T(n-1)和T(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).

最小跳转数组递归时间复杂度应为 O(n^n) 或 O(n!)

Minimum Jump Array Recursive Time Complexity should be O(n^n) or O(n!)

java

arrays

algorithm

time-complexity