LCS的蛮力方法及其时间复杂性[O(m*n)！?]

Question

我读了几本算法书籍，其中被告知最长常见子序列的蛮力方法以2^n为指数，这在时间复杂上是指数的。鉴于，我注意到，在应用蛮力技术时，它正在采用O（M n）（从我的个人观察中）。我想请您清楚地阅读我的方法，并牢记可视化，并在需要时提出进一步的澄清。我的方法如下： - 说我们有两个字符串 s1 =" ecdgi"， s2 =" abcdefghij"。现在，我正在做的是我选择了一个给定的字符串。例如，S1。对于i = 1至n（ n 是S1的最后一个索引），我正在采用每个值并与S2进行比较，以使得S1的单个字符，S2的字符。从数学上讲，ITH值正在检查所有jth值，最高为m（ m 是S2的最后一个索引）。在这里，如果我发现任何常见的角色，我只会从两个字符串中移动到下一个字符。然后只计算子序列。我通过运行 n 循环来计算S1中每个字符的所有可能子序列。最后，我计算最大的价值。从我的理解中，总体上需要o（m n）时间复杂性。所以我的问题是，"我的时间复杂性计算正确吗？"

跟踪：

i = 1，value = e，lcs = 3 [egi]

i = 2，value = c，lcs = 4 [cdgi]

i = 3，value = d，lcs = 3 [dgi]

i = 4，value = g，lcs = 2 [gi]

i = 5，value = 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（）？对于S2的S1和M/2的所有N/2的第2个成对，SO N/2 * M/2次
   • 现在让我们分析doit（）
   的复杂性
   • 它使用两个指示器通过两个字符串，因此其复杂性是O（n M）
   • 因此，总复杂性为O（n * m *（n m））或o（n^2 * m m^2 * n）