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

我已经阅读了一些算法书，其中被告知最长公共子序列的蛮力方法取2 ^ n，它是时间复杂度的指数。然而，我注意到当我使用我的蛮力技术的时候，它采取了o（mn）（从我的个人观察）。
我想请你清楚地阅读我的方法，并在脑海中形象化，如果需要的话，请提出进一步的澄清问题。
我的方法如下：-假设我们有两个字符串s1=“ecdgi”，s2=“abcdefghij”。
现在我要做的是，我选择其中一个给定的字符串比如说，s1。
对于i=1到n（n是s1的最后一个索引），我取每个值并与s2进行比较，这样对于s1的单个字符，我将检查s2的所有字符。从数学上讲，ith值是检查所有jth值，直到m（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 ;
           }
        }
     }
  }

}

最佳答案

你的算法是错误的考虑一下当s1=“aabaa”和s2=“aaaab”时，代码给出3，而lcs是4。
时间复杂度为O（n*m＊（n+m））
为什么？
好吧，让我们考虑最坏的情况，我们有s1是n/2'A'
字符和N/2“B”字符，S2是M/2“A”字符和
M/2“C”字符
现在如果忽略doIt（）函数循环本身，则给出O（n*m）
那么doit（）被调用了多少次？对于所有的n/2对，s1的第一个字符和s2的m/2，所以n/2*m/2次，或者如果我们把常数降为O（n*m）次
现在让我们分析doi（）的复杂性。
它使用类似于2个指针的东西来传递这两个字符串，因此它的复杂性是O（n+m）。
因此，总体复杂度为O（n*m（n+m））或O（n ^ 2×m +m ^ 2×n）。

关于algorithm - LCS的蛮力方法及其时间复杂度[O(m * n)!?]，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55207687/