Этот алгоритм грубой силы NP-сложный?

Вот алгоритм перебора, который мы используем в системе управления проектами для извлечения ключевых слов из рефератов. Какова временная сложность этого алгоритма перебора? Это NP-жесткий, NP-полный, в NP или в P?

Это алгоритм:

public static int search(String pattern, String text) {
  int M = pattern.length();
  int N = text.length();
  for (int i = 0; i < N - M; i++) {
    int j;
    for (j = 0; j < M; j++) {
      if (text.charAt(i+j) != pattern.charAt(j)) {
         break;
      }
    }
    if (j == M) {
      return i;
    }
  }
  return -1;
}

1 ответ

Начнем с того, что только проблемы могут быть в NP, или в NP- жестком, или в NP- неполном, или в P, поэтому не имеет смысла спрашивать, является ли ваш конкретный алгоритм NP- трудным или NP- полным.

Конкретный алгоритм, который у вас есть, - это простой алгоритм поиска строк. Учитывая текстовую строку длины m и строку шаблона длины n, она выполняется за время O((m - n + 1)n). Это полином по размеру входных строк, и поэтому эта проблема - проблема поиска строк - принадлежит классу P. Это также в NP, так как каждая проблема в P находится в NP, но неизвестно, является ли эта проблема NP- трудной или NP- неполной, потому что решение этого вопроса решит, будет ли P = NP.

Разумно спросить, когда вы обнаруживаете, что что-то грубо заставляет, слишком ли медленно работает ваше решение или можно решить проблему, которую вы пытаетесь решить, более эффективно, и для этого здорово посмотреть на проблему и увидеть то, что известно об этом. В вашем случае, есть лучшие алгоритмы для поиска строк; алгоритм Кнута-Морриса-Пратта работает в наихудшее время O(m + n), алгоритм Рабина-Карпа в среднем выполняется за время O (m + n) и очень прост в реализации, а алгоритм Бойера-Мура может бегать в сублинейное время во многих случаях. Однако тот факт, что ваш алгоритм перебора не так эффективен, как эти алгоритмы, не имеет ничего общего с NP- полнотой.

Другие вопросы по тегам