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

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

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

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

回答

相關問題