algorithm - 动态规划算法的时间和空间复杂度

Question

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

一个 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];
        }
}

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

谢谢

Answer 1

让我们执行代码:

注意递归堆栈的表示法。 1.2.3.表示第三次递归 countWaysDP(n-5) 第二次递归 countWaysDP(n -2) 的 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 <-

现在假设 调用一个方法是 O(1) 操作。此示例花费的总时间为:

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

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

递归堆栈将占用 O(n)，因为最大堆栈深度为 n + 3，您的 map 将占用 O(n) 空间。所以是的，SPACE 是 O(n + n) = O(n)。