如何计算算法的复杂度？

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

有人可以解释一下或帮我计算这个函数吗？我试过谷歌搜索但我只能找到简单的例子。（也许我的代码也很简单？）

谢谢！

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

我不太明白第二段代码要做什么，因为你的代码中有很多函数没有提供。也许你可以解释一下？

如何计算算法的复杂度？

How to calculate complexity of an algorithm?

algorithm

complexity-theory

time-complexity