动态规划算法的时间和space复杂度

Question

此算法来自 Cracking the Coding Interview，第 5 版，可在此处找到：https://www.geekbooks.me/book/view/cracking-the-coding-interview-5th-edition

A child 运行正在爬 n 步楼梯，可以跳 1 步、2 步或一次3个步骤。实现一种方法来计算 child 有多少种可能的方式可以运行上楼梯。算法：

 public static int countWaysDP(int n, int[] map) {
    if (n < 0) {
        return 0;
    } else if (n == 0) {
        return 1;
    } else if (map[n] > -1) {
        return map[n];
    } else {
        map[n] = countWaysDP(n - 1, map) + 
                 countWaysDP(n - 2, map) + 
                 countWaysDP(n - 3, map);
        return map[n];
        }
}

这个算法的时间和 space 复杂度是多少？我认为由于使用了记忆，因此存储了结果，因此不会像在纯递归方法中那样多次计算值。由于对 countWaysDP 进行了三次调用，因此时间复杂度为 O(3n)，这是 O(n) 的一个元素。 space 的复杂度为 O(n+n)，map 的大小为 1 n，递归调用堆栈为 1 n，这也是 O(n) 的一个元素。我的推理正确吗？

谢谢

Answer 1

关于您的算法：虽然您将结果存储在地图中，但您的算法每次都会进行 3 次递归调用，然后才将解决方案插入地图中。这意味着您不会重复使用中间结果。

为了重复使用，您需要从 n=1 开始，然后进行迭代，直到达到所需的步数。这样您就可以确保将结果重复用于所有较小的步骤：

for (int i = 1; i <= n; i++) {
  int current = map[i-1]; // you can make 1 step
  if (i > 1) 
    current += map[i-2]; // you can make 2 steps
  if (i > 2)
    current += map[i-3]; // you can make 3 steps
  map[i] = current;
}
return map[n];

现在的复杂性：

我们使用一张地图，最后有 n 个条目。因此 space 复杂度为 O(n)。

我们从1到n迭代一次进行计算。因此时间复杂度也是O(n).

Answer 2

使用记忆的简单解决方案（O(N) 时间复杂度和 space 复杂度）:

public static int countWaysDP(int n, int[] map) {
    map[1] = 1; // when n = 1, answer is 1
    map[2] = 2; // when n = 2, answer is 2, (1+1) and (2)
    map[3] = 4; // (1+1+1), (1+2), (2+1), (3)

    for(int i = 4;i <= n; i++)
    {
        map[i] = map[i-1] + map[i-2] + map[i-3]; 
    }

    return map[n];
}

希望对您有所帮助！！！

Answer 3

让我们执行代码：

注意递归栈的表示法。 1.2.3. 表示 第三次递归 countWaysDP(n-5) of second递归 countWaysDP(n-2) of countWaysDP(n).

Consider n=6

1. countWaysDP(6)
1.1. countWaysDP(5)
1.1.1. countWaysDP(4)
1.1.1.1. countWaysDP(3)
1.1.1.1.1. countWaysDP(2)
1.1.1.1.1.1. countWaysDP(1)

1.1.1.1.1.1.1. countWaysDP(0) //returns 1
1.1.1.1.1.1.2. countWaysDP(-1) //returns 0
1.1.1.1.1.1.3. countWaysDP(-2) //returns 0                        -> map[1] = 1 <-

1.1.1.1.1.2. countWaysDP(0) //return 1
1.1.1.1.1.3. countWaysDP(-1) //return 0                           -> map[2] = 2 <-

1.1.1.1.2. countWaysDP(1) //already claculated, returns map[1]
1.1.1.1.3. countWaysDP(0) //returns 1                             ->map[3] = 4 <-

1.1.1.2. countWaysDP(2) //already present, returns map[2]
1.1.1.3. countWaysDP(1) //already present, returns map[1]         -> map[4] = 7 <-

1.1.2. countWaysDP(3) //already present, returns map[3]
1.1.3. countWaysDP(2) //already present, returns map[2]           -> map[5] = 13 <-

1.2. countWaysDP(4) //already present, returns map[4]
1.3. countWaysDP(3) //already present, returns map[3]             -> map[6] = 24 <-

现在假设involking a method is O(1)操作。此示例花费的总时间为：

6 + 3 + (2 + 2 + 2 + 2 + 2) = 19

所以是的，您关于 TIME 的说法是正确的。它的 3n 作为最左边的递归路径采用 O(n)，然后所有其他调用都是 O(2n)。

递归堆栈将采用 O(n)，因为 最大堆栈深度为 n + 3，而您的映射将采用 O(n) space。所以是的，SPACE 是 O(n + n) = O(n).

动态规划算法的时间和space复杂度

Time and space complexity of dynamic programming algorithm

algorithm

dynamic-programming

memoization