Является ли этот алгоритм грубой силы NP-hard?

Question

Вот алгоритм грубой силы, который мы используем в системе управления проектами для извлечения ключевых слов из тезисов. Какова временная сложность алгоритма перебора? Является ли он 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; 
} 

Answer 1

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

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

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