Этот алгоритм грубой силы 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- полнотой.