如何計算算法的複雜性？

Question

我試圖計算算法的複雜性，但我不知道如何做到這一點。我知道如何解決簡單的算法，但我正在努力與遞歸。

有遞歸的代碼：

static int F(int m, int n) 
    { 
     if (n == 0) 
      return m; 

     if (m == 0 && n > 0) 
      return n; 

     else 
      return Math.Min((1 + F(m - 1, n)), Math.Min((1 + F(m, n - 1)), (D(m - 1, n - 1) + F(m - 1, n - 1)))); 
    } 

有人可以解釋我還是幫我計算這個功能呢？我試過Google搜索它，但我只能找到簡單的例子（也許我的代碼也很簡單？）

謝謝！

Answer 1

我不知道D函數在你的第一段代碼中。我會認爲它是一個不變的功能。

您的代碼的第一部分等同於以下代碼。

static int F(int m, int n) 
{ 
    if (n == 0 || m == 0) 
     return n + m; 
    else 
     return Math.Min((1 + F(m - 1, n)), Math.Min((1 + F(m, n - 1)), (D(m - 1, n - 1) + F(m - 1, n - 1)))); 
} 

這是一個有點難以用兩個參數來計算遞歸函數的時間複雜度，但我們可以大致估算出它。我們有以下等式。

T(n, m) = T(n-1, m) + T(n, m-1) + T(n-1, m-1) 

我們可以發現，方程是非常相似的binomial coefficient的迴歸方程，但更大的結果。這告訴我們算法的時間複雜度是一個指數函數，這是非常緩慢的。

但實際上，您可以使用一些技巧將其時間複雜度降低到O（mn）。

bool calculated[MAX_M][MAX_N]; 
int answer[MAX_M][MAX_N] 

static int F(int m, int n) 
{ 
    if (n == 0 || m == 0) 
     return n + m; 
    else 
    { 
     if (calculated[m][n] == false) 
     { 
      answer[m][n] = Math.Min((1 + F(m - 1, n)), Math.Min((1 + F(m, n - 1)), (D(m - 1, n - 1) + F(m - 1, n - 1)))); 
      calculated[m][n] = true; 
     } 
     return answer[m][n]; 
    } 
} 

我不能完全理解第二段代碼要做什麼，因爲在代碼中沒有提供很多功能。也許你可以解釋一下？