带记忆的循环内递归的运行时复杂度

Question

我想知道如何确定以下代码的时间复杂度，使用带记忆的自顶向下动态规划方法（注意 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];
}

Answer 1

问题 :

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

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

答案：该函数的复杂度为 O(n * n)。

直觉：

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

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

解释：

假设矩阵的大小为 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]`

[注意] i = 0 是函数初始化时的基本情况 A 和 returns 0.

带记忆的循环内递归的运行时复杂度

Runtime complexity of recursion inside loop with memoization

java

c

algorithm

dynamic-programming

topdown