algorithm - LCS 的强力方法及其时间复杂度 [O(m*n)!?]

Question

我读过几本算法书籍，其中提到最长公共(public)子序列的暴力方法需要 2^n，其时间复杂度呈指数级。然而，我注意到，当我应用蛮力技术时，它需要 O(mn) (根据我个人的观察)。 我想请求您清楚地阅读我的方法并在脑海中想象，并在需要时提出问题以进一步澄清。 我的方法如下:-假设我们有两个字符串 s1 = "ECDGI"， s2 = "ABCDEFGHIJ"。 现在我正在做的是选择给定的字符串之一。比如说，s1。 对于 i = 1 到 n(n 是 s1 的最后一个索引)，我正在获取每个值并与 s2 进行比较，对于 s1 的单个字符，我正在检查所有s2 的字符。从数学上讲，第 i 个值检查直到 m 的所有第 j 个值(m 是 s2 的最后一个索引)。在这里，如果我找到任何共同字符，我只需移至两个字符串中的下一个字符。然后只需计算子序列即可。我通过运行 n 循环来计算 s1 中每个字符的所有可能子序列。最后，我计算最大值。 根据我的理解，总体时间复杂度为 O(mn)。 所以我的问题是，“我的时间复杂度计算正确吗？”

追踪:

i = 1，值 = E，lcs = 3 [EGI]

i = 2，值 = C，lcs = 4 [CDGI]

i = 3，值 = D，lcs = 3 [DGI]

i = 4，值 = G，lcs = 2 [GI]

i = 5，值 = I，lcs = 1 [I]

答案是 = 4(最大 lcs)

我的代码如下!

import java.util.*;
public class Main {
      static int count;
      static String s1 = "ECDGI"; // you can try with "EEE" or etc. 
      static String s2 = "ABCDEFGHIJ"; // you can try with "EEE" or etc.
  public static void main(String[] args) {
 LinkedList<Integer> ll = new LinkedList<>();
      for(int i =0; i<s1.length();i++){
      int t = i;
      count = 0; 
       for (int j=0; j<s2.length();j++){
         if(s1.charAt(t)==s2.charAt(j)){
           count++; 
            doIt(t+1,j+1);
            break ; 
        }
       }
        ll.add(count);
      }
      System.out.println(ll); // printing the whole LinkedList
      System.out.println(Collections.max(ll)); // taking the maximum value 
  }
  public static void doIt(int a, int b){
 for ( ; a<s1.length(); a++){
        int t = b ; 
        for (; t<s2.length(); t++){
          if (s1.charAt(a) == s2.charAt(t)){
           count++; 
           b=t+1; 
           break ; 
           }
        }
     }
  }

}

Answer 1

1. 你的算法是错误的。考虑当 s1 = "AABAA"且 s2 = "AAAAB"时的情况，您的代码给出 3，但 LCS 为 4。

2. 时间复杂度为 O(n * m * (n+m))

   • 为什么？

   • 好吧，让我们考虑最坏的情况，其中 s1 是 n/2 'A' 字符和 n/2 个“B”字符，并且 s2 是 m/2 个“A”字符并且 m/2 'C' 字符

   • 现在，如果我们忽略 doIt() 函数循环本身，则给出 O(n * m)
   • 那么 doIt() 被调用了多少次？对于 s1 的所有 n/2 个第一个字符和 s2 的 m/2 个字符，因此 n/2 * m/2 次，或者如果我们删除常量 O(n * m ) 次
   • 现在让我们分析 doIt() 的复杂性
   • 它使用类似 2 个指针来传递两个字符串，因此其复杂度为 O(n+m)
   • 因此总复杂度为 O(n * m * (n+m)) 或 O(n^2 * m + m^2 * n)