递归函数的时间复杂度

Question

我正在用朴素的递归解决 LCS 问题。

我不明白为什么最坏情况下的复杂度是2^n

/* A Naive recursive implementation of LCS problem 
   so what is the recurrence relation for this program */

// Returns length of LCS for X[0..m-1], Y[0..n-1]

int lcs( char *X, char *Y, int m, int n )
{

    if (m == 0 || n == 0) // if length of any sequence becomes 0 return 0
        return 0;

    if (X[m-1] == Y[n-1]) // if last elements are same then it must be
                          // in longest sequence so it is appended to lcs
        return 1 + lcs(X, Y, m-1, n-1);

    // what is the recurrence relation for this function

    else
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

谁能解释一下递归关系

Answer 1

假设n = max(m, n)，您可以将每个函数调用视为树中的一个节点。在最坏的情况下，对于字符串中的任何实例，X[m-1] != Y[n-1]。在那种情况下，对于树中的每个节点，我们进行两次函数调用，或者向下分支到两个子节点。因此，我们正在构建一个深度为 n 的完全填充的二叉树。这个深度的二叉树将有 2^n - 1 个节点（https://math.stackexchange.com/questions/141783/the-maximum-number-of-nodes-in-a-binary-tree-of-depth-k-is-2k-1-k-geq1），并且由于我们将节点定义为函数调用，因此运行时间约为 2^n - 1 = > O(2^n).

递归函数的时间复杂度

time complexity of recursive function

recurrence

time-complexity