оцениваю мой код big-O, наивное сопоставление с образцом
Я пытаюсь решить упражнение 32.1-2 из Книги CLRS, которое касается строковых алгоритмов, поиска наивного шаблона
Предположим, что все символы в шаблоне P разные. Покажи как ускориться
NAIVE-STRING-MATCHER для запуска во времени O (n) для 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;
?>
Я, конечно, сократил время выполнения для этого конкретного экземпляра, но представьте себе, что в худшем случае для Text со всеми его символами, установленными в ‘a’, я буду погружаться во второй цикл каждый раз, когда O (k * n).
Что такое биг-о алгоритма?
и могу ли я получить более эффективное решение?
Решение
Вы также правильно поняли идею («поскольку сопоставление с образцом не может перекрываться с другим»).
Нечто подобное должно работать для основного цикла:
for($i=0;$i<$n - $k ;$i++){
for($j=0; $j<$k; $j++){
$last_matched = $j + $i;
if($b[$j + $i] == $a[$j])
$bool = true;
else {
$bool = false;
break;
}
}
if($bool){
echo "Found at index: ".$i."<br>";
$counter++;
}
// this line is important
$i = $last_matched + 1;
}
Обратите внимание на важную строку.
Здесь мы говорим алгоритму начать следующую попытку сопоставления после того, как наше предыдущее совпадение не удалось (или закончилось).
Это связано с тем, что в шаблоне есть разные символы, и нет никакой возможности, чтобы, если вы уже сопоставили j символов, а затем не смогли сопоставить j + 1, реальное совпадение будет перекрывать эту область (если они перекрываются, некоторые символы в шаблоне должны быть одинаковыми , что является противоречием).
Теперь сложность измененного алгоритма будет O (n). Это связано с тем, что условие if во внутреннем цикле будет выполняться только один раз для каждого символа текста (помните, что после того, как внутренний цикл завершается или прерывается, мы запускаем внешний цикл после его последней позиции).
П.С .: Умножение на сложность циклов часто правильно, но вы не всегда получаете максимально возможный предел.
Другие решения
Других решений пока нет …