Метод грубой силы для LCS и его временная сложность [O (m * n) !?] - PullRequest
Новая
       21

Метод грубой силы для LCS и его временная сложность [O (m * n) !?]

1 голос
/ 17 марта 2019

Я прочитал несколько книг по Алгоритмам, где сказано, что метод грубой силы Самая длинная общая подпоследовательность занимает 2 ^ n, что экспоненциально по временной сложности.Принимая во внимание, что я заметил, что, применяя технику грубой силы, он берет O (m n) (из моего личного наблюдения).Я хотел бы попросить вас, пожалуйста, прочитайте мой подход четко и наглядно представьте и задайте вопрос для дальнейшего уточнения, если это необходимо.Мой подход следующий: - скажем, у нас есть две строки s1 = "ECDGI", s2 = "ABCDEFGHIJ".Теперь я выбрал одну из указанных строк.Например, s1.для i = 1 до n ( n - последний индекс s1), я беру каждое значение и сравниваю с s2 таким образом, что для одного символа s1 я проверяю все символыиз s2.Математически, i-е значение проверяет все j-е значения до m ( m - последний индекс s2).Здесь, если я найду какой-либо общий символ, я просто перейду к следующему символу из обеих строк.Тогда просто вычислите подпоследовательность.Я вычисляю все возможные подпоследовательности для каждого символа из s1, выполняя n циклы.Наконец, я вычисляю наибольшее значение.Насколько я понимаю, это занимает O (m n) сложность времени в целом.Поэтому мой вопрос: «Правильно ли рассчитан мой временной комплекс?»

Трассировка:

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 ; 
           }
        }
     }
  }

}

1 Ответ

1 голос
/ 17 марта 2019

  1. Ваш алгоритм неверен.Рассмотрим случай, когда s1 = "AABAA" и s2 = "AAAAB", ваш код дает 3, но LCS равен 4.

  2. Сложность по времени O (n * m * (n +м))

    • Почему?

    • Хорошо, давайте рассмотрим наихудший случай, когда у нас s1 это n / 2 символа 'A' и n / 2 символа 'B', а s2 это m / 2 символа 'A'и m / 2 символов 'C'

    • Теперь, если мы проигнорируем сами циклы функции doIt (), получим O (n * m)
    • Сколько раз вызывается doIt ()?хорошо для всех пар n / 2 первых символов s1 и m / 2 для s2, поэтому n / 2 * m / 2 раза, или если мы отбрасываем константы O (n * m) раз
    • Теперь давайте проанализируем сложностьof doIt ()
    • Используется что-то вроде 2 указателей для прохождения обеих строк, поэтому его сложность составляет O (n + m)
    • Таким образом, общая сложность составляет O (n * m * (n + m).)) или O (n ^ 2 * m + m ^ 2 * n)
...