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

Question

我读过几本算法书籍，其中提到 最长公共子序列 的蛮力方法需要 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

你的算法有误。考虑 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 ) 次
- 现在让我们分析一下 doIt() 的复杂度
- 它使用类似 2 个指针的东西来传递两个字符串，所以它的复杂度是 O(n+m)
- 所以总复杂度是 O(n * m * (n+m)) 或 O(n^2 * m + m^2 * n)

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

Brute Force Approach for LCS and its Time Complexity [O(m*n)!?]

algorithm

time-complexity

analysis

lcs