Как анализировать временную сложность этого кода?

Это мой Принимается код этого 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)? Я не думаю, что здесь может применяться магистерская теорема, потому что каждая подзадача не имеет такого же размера (но я не уверен в этом).

источник

2016-07-06 shole

Вы должны решить dp. Подумайте о снижении вверх. Если вам нужно вычислить значение dp [n] [m] [k], тогда все его под-проблемы уже решены. Тогда время, необходимое для вычисления этого значения, будет max (n, m) * k. В целом будет n * m * k таких значений, которые вы должны вычислить. Таким образом, общая временная сложность будет равна O (n * m * k * max (n, m) * k).

источник

2016-07-07 08:33:03 VikramBishnoi

Спасибо, это имеет смысл, но является ли этот метод анализа/мышления общим для всех проблем DP? – shole

Временная сложность решения динамического программирования будет одинаковой, если вы идете сверху вниз или снизу вверх. Поэтому да, вы можете использовать этот метод для вычисления временной сложности в целом для решений DP. – VikramBishnoi

(Post другая возможная мысль, которая может помочь)

После обсуждали с моим одноклассником, он предложил очень простую мысль:

Think рекурсию как делать простой ДФС

Затем сложность O (| V | + | E |)

Здесь | V | = nmk, | E | = | В | (п + тк)

Таким образом, общая сложность О (НМК + п^2mk^2 + нм^2k^2) = O (макс (п, т) * НМК^2)

Мне нравится это моделирование, но я не уверен, что это общий метод анализа для таких решений DP, поэтому я принимаю ответ @VikramBishnoi, который дает такую же сложность в конце.

источник

2016-07-07 08:45:35 shole

Как анализировать временную сложность этого кода?

ответ

Смежные вопросы