我試圖從CLRS的書,這是關於字符串算法,天真模式搜索估計我的代碼大O,天真模式匹配
假設解決練習32.1-2,在模式P中的所有字符是不同的。顯示如何加速 NAIVE-STRING-MATCHER在n字符文本上在時間O(n)上運行。
所以我試圖優化我想出的天真蠻力解決方案,但我不認爲我可以做得更好,以減少O(n)的整體運行時間。
<?php
//naive search
$a = array('a', 'b', 'u', 'c');
$b = array('a','b','u','c','a','b','u','c','b','a','b','u','c','b', 'a', 'b','c');
//index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
$n = count($b);
$k = count($a);
$counter = 0;
for($i=0;$i<$n - $k ;$i++){ // big- O (n)
//since its "exact string matching problem" i am testing here so i don't dive into second loop unless the ith character of B is matching the first char of the pattern
if($b[$i] == $a[0]){
for($j=$i; $j<$k; $j++){ // big O(k)
if($b[$j] == $a[$j])
$bool = true;
else {
$bool = false;
break;
}
}
if($bool){
echo "Found at index: ".$i."<br>";
$counter++;
}
// since pattern match cant overlap with another one, so when one is found jump by K iteration, here is all what I could do about the pattern's value being distinct, is there any possible optimization I can do
$i = $i + $k - 1;
}
}
echo $counter;
?>
我肯定減少了運行時間爲這個特定實例,但是想象一下最壞的情況下,其所有字符設置爲「A」一文中,我將深入第二循環的每一個是O時間( K * N)。
什麼是算法的大O? ,我可以得到更有效的解決方案嗎?
關於你寫的最後一個音符,因爲我知道我們用Θ來表示一個緊上限&O來表示一個上限。如果練習要求Θ不是O,我的解決方案會是最佳的嗎? –
我認爲我沒有理解這個問題,becuz最佳模式匹配算法「KMP」運行在O(m + n) –
交換使用O和Thera的人(雖然他們是不同的)。我的發言也持有theta符號。 – usamec