1

我想知道如何确定以下代码的时间复杂度，使用自上而下的动态编程方法和记忆（注意 i，k，d 可以是任何整数值）：

solve(i, k, d) {
    if (k >= d) {
        A[i][k] = 0;
        return 0;
    }

    if (i == 0) {
        A[i][k] = 0;
        return 0;
    }

    if (A[i][k] == null) {
        for (int j = 0; j < k + 1; j++) {
            A[i][k] = solve(i - 1, (k + 1 - j), d);
        }
    }

    return A[i][k];
}
4

1 回答 1

1

问题：

solve(i - 1, (k + 1 - j), d)

当 j = 0 时会给出超出范围的错误，因为A索引应该从 0 到 K [K 是最大索引]

解答： 该函数将给出 O(n * n) 复杂度。

直觉：

（很明显，最坏的情况是没有解决方案的情况，所以我专注于此）

由于递归调用是在将值放入记忆缓存之前进行的，因此最后一个（最短的）后缀将首先被缓存。这是因为该函数首先使用长度为 N 的数组调用，然后使用长度为 N-1 的数组调用自身，然后 .... 使用长度为 0 的数组进行缓存并返回，然后长度为 1 的数组被缓存并返回，...，长度为 N 的数组被缓存并返回。

解释 ：

假设矩阵 I x K 的大小并考虑最坏情况，

[注意]在最坏的情况下，函数调用将从矩阵的右下角开始

A初始化发生在两种情况下：

  • k >= d
  • i == 0

[注意]在最坏的情况下，k总是小于d.

For loop for `(I, K)`
- Recursion call `for (i-1, k:[K to 0])` 
- Update value for `A[i, k]`

[注意]A i = 0 是函数初始化并返回 0的基本情况。

于 2017-11-06T00:21:55.350 回答