Wie analysiert man die zeitliche Komplexität dieses Codes?

Question

Es ist mein akzeptierter Code für diese Codeforces Problem: Education Round 1E

Durch Erfahrung, ich es sicher lösen kann, aber ich es immer für mich da ist schwer die Zeit Komplexität dieser Art von Algorithmus (in der Regel Rekursion in DP) zur Analyse

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

Was ist die übliche Praxis, die Komplexität der Funktion wie DP(N,M,K) Analyse? Ich glaube nicht, dass hier der Hauptsatz angewendet werden kann, weil jedes Teilproblem nicht die gleiche Größe hat (aber ich bin mir nicht sicher).

Answer 1

Sie müssen die dp Matrix zu lösen. Überlege, ob du von unten nach oben gehen willst. Wenn Sie den Wert dp [n] [m] [k] berechnen müssen, sind alle seine Teilprobleme bereits gelöst. Dann ist die Zeit, die benötigt wird, um diesen Wert zu berechnen, max (n, m) · k. Insgesamt wird es n * m * k solche Werte geben, die Sie berechnen müssen. Somit wird die gesamte Zeitkomplexität O (n * m * k * max (n, m) * k) sein.

Answer 2

(Beitrag eine weitere mögliche Gedanken, die dazu beitragen kann)

Nachdem mit meiner Mitschüler diskutiert, schlug er einen sehr einfachen Gedanken:

Denken die Rekursion als eine einfache DFS tun

Dann ist die Komplexität O (| V | + | E |)

Hier | V | = nmk, | E | = | V | (nk + mk)

So Gesamtkomplexität ist O (NMK + n^2MK^2 + nm^2k^2) = O (max (n, m) * nmk^2)

Ich mag diese Modellierung, aber ich bin mir nicht sicher, das ist eine allgemeine Analysemethode für solche DP-Lösungen, daher akzeptiere ich @VikramBishnoi Antwort, die die gleiche Komplexität am Ende gibt.