c++ - 这个递归函数的时间复杂度是多少

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 7 年前。

Improve this question

我遇到了以下代码，该代码用于获取两个给定字符串的最长公共(public)子序列。它使用递归，时间复杂度为2^n，但我不知道这个结果是如何生成的，谁能帮忙分析一下，谢谢。

/* A Naive recursive implementation of LCS problem */
#include<stdio.h>
#include<stdlib.h>

int max(int a, int b);

/* 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)
     return 0;
   if (X[m-1] == Y[n-1])
     return 1 + lcs(X, Y, m-1, n-1);
   else
     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

/* Utility function to get max of 2 integers */
int max(int a, int b)
{
    return (a > b)? a : b;
}

/* Driver program to test above function */
int main()
{
  char X[] = "AGGTAB";
  char Y[] = "GXTXAYB";

  int m = strlen(X);
  int n = strlen(Y);

  printf("Length of LCS is %d\n", lcs( X, Y, m, n ) );

  getchar();
  return 0;
}

Answer 1

最坏的情况是调用lcs将导致两次调用 lcs :

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

此外，如果 I=m+n那么， child 打电话总是满足I_child <= I_parent - 1 ，参见可能的递归调用的参数:

return 1 + lcs(X, Y, m-1, n-1);

和

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

所以如果 C(I)是 lcs(X, Y, m, n) 的复杂度, C(I) <= 2C(I - 1)+O(1) (抛开递归调用，你只执行比较，只要整数有界，就可以在恒定时间内进行比较，而且它们实际上也会因为 if 语句而跳转，但你也可以假设它是恒定时间)< br/>所以我们有:

C(0) = O(1)
C(I) <= 2C(I - 1) + O(1) <= O(1) + 2O(1) + 2^2O(1)+....+2^IO(1)

因此

C(I) = O(2^I)

或以 m 的形式表示和n :

C(I) = O(2^max(m, n))

(编辑:这个界限可能会得到改善)