c++ - 以下递归解决方案的大O

Question

我写了下面的代码来寻找两个字符串之间的最小删除距离

enter code here
#include <iostream>
#include <string>

using namespace std;
int  DeletionDistance(const string& str1, const string& str2, int len1, int  
len2){
int index1=0;
int index2=0;
int count=0;
int str1len=str1.length();
int str2len=str2.length();
//calculate the base case if a string is empty, the deletion distance is the 
length of the other string
//since we need to delete all the other chars from the non empty string in 
order to match the two strings
if(str1len<=0)
  return str2len;
else if(str2len<=0)
  return str1len;
else{
//the strings are non empty. Recursively calculate the min del distance 
  if(str1[index1]==str2[index2]){
     //the chars match , hence the deletion distance would depend on the 
       remaining chars in both strings
      return DeletionDistance(str1.substr(index1+1,len1), 
                              str2.substr(index2+1,len2), len1, len2);  
  }
  else
    //the chars dont match 
    return (1+min(DeletionDistance(str1.substr(index1+1,len1), 
                                   str2.substr(index2,len2), len1, len2),
                  DeletionDistance(str1.substr(index1,len1), 
                                   str2.substr(index2+1,len2), len1, 
                                   len2)));
    }
}

 int deletionDistance( const string& str1, const string& str2 ) 
 {
  int len1 = str1.length();
  int len2 = str2.length();
  return DeletionDistance(str1, str2, len1, len2);

 }

在这段代码中，我们递归地计算两个字符串之间的最小删除距离，如何计算时间和空间复杂度？ 有人告诉我这个解决方案的时间和空间复杂度是 O(ab) 其中， a = 字符串 1 的 len b = 字符串 2 的 len 我真的很感激关于如何开始为这样的递归解决方案计算 Big O 的一些解释或指示。 我能够为更简单的递归解决方案(如 Fibonacci 系列、阶乘等)计算 bigO，但这打败了我。

Answer 1

您的代码的复杂度为 O(2 ^ (|A| + |B|) )，其中 |A| 和|B|分别是第一个和第二个字符串的大小。

这样做的原因是，在最坏的情况下，您的递归将在到达两个字符串中的最后一个字符时返回。在您的代码中，每次您在第一个或第二个字符串中前进一步。所以一般来说，您的递归深度为 (|A| + |B|)，并且您的代码包含 2 递归调用。

如评论中所述，您可以使用动态规划实现 O(|A| * |B|) 的复杂度。这是一个不错的 tutorial这将引导您完成它。您的问题接近最长公共(public)子序列问题 (LCS)。