Я читал книгу, в которой говорится, что сложность времени внешних циклов равна O (n-m), тогда как для внутреннего цикла книги дают объяснение как
«Внутренний цикл while вращается не более m раз, и потенциально
гораздо меньше, когда сопоставление с образцом не удается Это, плюс два других
заявления, лежит внутри внешнего цикла for. Внешний цикл вращается
самое большее n − m раз, так как полное выравнивание невозможно, как только мы получим
слишком далеко справа от текста. Временная сложность вложенных циклов
умножается, так что в худшем случае время работы O ((n — m) (m +)
2)). «
Я не понял, по какой причине временная сложность внутреннего цикла составляет O (m + 2) вместо O (m)? Пожалуйста помоги.
int findmatch(char *p, char *t)
{
int i,j; /* counters */
int m, n; /* string lengths */
m = strlen(p);
n = strlen(t);
for (i=0; i<=(n-m); i=i+1) {
j=0;
while ((j<m) && (t[i+j]==p[j]))
j = j+1;
if (j == m) return(i);
}
return(-1);
}
Цикл while:
while ((j<m) && (t[i+j]==p[j]))
j = j+1;
O (м), то у вас есть +2 от (other statements
):
j=0; // + 1
// loop
if (j == m) return(i); // + 1
Других решений пока нет …