如何计算算法的复杂性？

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

我不能完全理解第二段代码要做什么，因为在代码中没有提供很多功能。也许你可以解释一下？