這個蠻力算法NP-hard？

下面是我們在項目管理系統中使用的一種蠻力算法，用於從摘要中提取關鍵字。那個蠻力算法的時間複雜度是多少？在NP中還是在P中，是NP-NP還是NP-complete？這個蠻力算法NP-hard？

這是算法：

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

來源

2014-10-09 poo

標題語法不完全清楚，請查看... – MarcoS 2014-10-09 07:49:47

在您的代碼中，存在兩個嵌套for循環。如果M足夠小或M在有限範圍內變化，則時間複雜度爲N的階數。如果M變化很大，則時間複雜度爲（N * M）的階數。 – 2014-10-09 07:57:49

我想知道NP硬（非確定性多項式），NP完全（非確定性，P型（多項式））這類問題，當我使用模式匹配的bruite force算法從摘要中分析關鍵字時，文本文件...我如何決定在什麼類別的算法將來？ – poo 2014-10-09 09:45:45

首先，僅問題可以在NP，或NP -hard，或NP -complete，或在P ，因此，詢問您的特定算法是否是完整的並不重要。

你有特定的算法是天真的字符串搜索算法。給定長度爲m的文本字符串和長度爲n的模式字符串，它在時間O（（m-n + 1）n）中運行。這是輸入字符串大小的多項式，所以這個問題 - 字符串搜索問題 - 屬於P。這也是在NP因爲P的每一個問題是NP，但它不知道這個問題是否NP -hard或NP -complete，因爲要解決這個問題，將決定是否P = NP。

當你發現自己蠻橫的東西，你的解決方案是否太慢，或者你試圖解決的問題是否可以更有效地解決時，這是很有道理的，因此查找問題非常好並查看關於它的信息。在你的情況下，有更好的字符串搜索算法; Knuth-Morris-Pratt算法運行在最壞情況時間O（m + n），Rabin-Karp算法平均運行時間爲O（m + n），並且非常容易實現，Boyer-Moore算法可以在很多情況下，在非線性時間運行。然而，事實上你的蠻力算法不如這些算法那樣高效，完全沒有任何事情要做。

來源

2017-07-27 22:09:09 templatetypedef

這個蠻力算法NP-hard？

回答

相關問題