蛮力字符串的模式匹配分析，平均

我有蛮力字符串模式搜索算法如下：蛮力字符串的模式匹配分析，平均

public static int brute(String text,String pattern) { 
int n = text.length(); // n is length of text. 
int m = pattern.length(); // m is length of pattern 
int j; 
for(int i=0; i <= (n-m); i++) { 
    j = 0; 
    while ((j < m) && (text.charAt(i+j) == pattern.charAt(j))) { 
     j++; 
    } 
    if (j == m) 
    return i; // match at i 
    } 
    return -1; // no match 
} // end of brute()

虽然anlaysising上述算法笔者在这里提到的最坏情况和平均情况。

我承担了最糟糕的情况下的表现，但对于平均水平作者是如何带着O（m + n）表现的？在这里需要帮助。

蛮力模式匹配在最坏的情况下运行时间O（mn）。

普通文本大多数搜索的平均值为O（m + n），非常快。更一般情况的

举例： T：“这样的字符串搜索的例子是标准的” 病人：“存储”

感谢您的时间和帮助

来源

2013-03-22 venkysmarty

什么他指与O(m+n)是在正常情况下会发生的部分匹配。

例如，你的正常情况下，你会得到：

T: "a string searching example is standard" 
P: "store"

迭代：

O(38 + 5) == 43 
a -  no match (1) 
space - no match (2) 
    s  - match (3) 
    t  - match (4) 
    r  - no match (5) 
t  - no match (6) 
r  - no match (7) 
i  - no match (8) 
n  - no match (9) 
g  - no match (10) 
space  - no match (11)

等等

我缩进内部循环，使之更容易理解。

最终，你已经检查了所有的m这是O(m)，但部分匹配意味着你要么检查了所有的n这是O(n)（发现完全匹配），或至少足以charactors等于charactors量在n（仅部分匹配）。

总的这样会产生O(m+n)的时间。

最好的情况是O(n)如果比赛是在m的最开始。

来源

2013-03-22 06:39:32 Serdalis

蛮力模式匹配在最坏的情况下运行时间O（mn）。

普通文本大多数搜索的平均值为O（m + n），非常快，为。

请注意，对于相同的算法，您不能有2个Big-O。

似乎正在申请蛮力窗口移算法，

时间=（M-N + 1）M

最坏的情况是，当你有m = 1时，Ò （纳米）

最好的情况是，当你有m = n时，Ω（米）

来源

2013-03-22 07:00:31

问题问解释平均情况 – 2013-03-22 07:08:23

大O是上限。最好的，最差的和平均的情况都可以有上限。所以你可以使用big-O。该算法本身也可以具有上限，这与最坏情况相同。 – Dukeling 2013-03-22 07:10:48

那么，平均使用（不是平均情况）是其中m有Ω（log（n）） – 2013-03-22 07:42:57

蛮力字符串的模式匹配分析，平均

回答

相关问题