如何分析这段代码的时间复杂度？

Question

这是我为这个 Codeforces 问题接受的代码：Education Round 1E

凭经验，我可以自信地解决，但我总是发现我很难分析这种算法的时间复杂度（通常是DP中的递归）

#include<bits/stdc++.h>
using namespace std;

int t;
int N,M,K;
int dp[32][32][52];

int DP(int n, int m, int k){
    if(k > n*m) return 1<<28;
    if(k == n*m || k <= 0) return 0;
    if(dp[n][m][k] != 1<<28) return dp[n][m][k];

    for(int i=1; i<n; i++)
        for(int j=0; j<=k; j++)
            dp[n][m][k] = min(dp[n][m][k],  DP(i, m, j) + DP(n-i, m, k-j) + m*m);

    for(int i=1; i<m;i++)
        for(int j=0; j<=k; j++)
            dp[n][m][k] = min(dp[n][m][k], DP(n, i, j) + DP(n, m-i, k-j) + n*n);

    return dp[n][m][k];
}

int main() {
    cin >> t;

    for(int i=0; i<32;i++) for(int j=0; j<32;j++) for(int k=0; k<52;k++) dp[i][j][k] = 1 << 28;
    while(t--){
        cin >> N >> M >> K;

        cout << DP(N,M,K) << endl;
    }
    return 0;
}

像DP(N,M,K)这样分析函数复杂度的常见做法是什么？我不认为主定理可以应用在这里，因为每个子问题的大小都不相同（但我不确定）。

Answer 1

您必须求解 dp 矩阵。考虑自下而上。如果你必须计算dp[n][m][k]的值，那么它的所有子问题都已经解决了。然后，计算该值所需的时间将为 max(n,m)*k。总的来说，你必须计算 n*m*k 个这样的值。因此，整体时间复杂度将为 O(n*m*k*max(n,m)*k).

Answer 2

（Post 另一个可能有帮助的想法）

和我同学讨论后，他提出了一个很简单的想法：

将递归视为简单的 DFS

那么复杂度是O(|V| + |E|)

这里|V| = nmk, |E| = |V|(nk+mk)

所以总复杂度是 O(nmk + n^2mk^2 + nm^2k^2) = O(max(n,m)*nmk^2)

我喜欢这种建模，但我不确定这是否是此类 DP 解决方案的通用分析方法，因此我接受@VikramBishnoi 的回答，它最后给出了相同的复杂度。

如何分析这段代码的时间复杂度？

How to analysis the time complexity of this code?

recursion

code-analysis

dynamic-programming

time-complexity

c++14