運行時複雜的遞歸內循環與記憶

我想知道如何確定下面的代碼的時間複雜度，使用自上而下的動態編程方法與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

運行時複雜的遞歸內循環與記憶

回答

相關問題