这个蛮力算法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？

回答

相关问题