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

我想知道如何确定下面的代码的时间复杂度，使用自上而下的动态编程方法与memoization（请注意，我可以是任何整数值）：运行时复杂的递归内循环与记忆

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

来源

2017-11-04 stackyyflow

嗯基例。你错过了一个return语句。但是，为什么不在'j = 0'时开始第一个分支并跟踪发生了什么 - 它在min（i，d-k）步骤后终止。 – MFisherKDX

问题：

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

会给出界错误的j = 0时为A指数应该从0到K [K为最大索引]

答案：函数会给出O（n * n）的复杂度。

直觉：

（很显然，最坏的情况是在一个地方有没有解决办法，所以我重点说）

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

说明：

假设矩阵1×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并返回0

来源

2017-11-06 00:21:55

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

回答

相关问题