определение сложности времени

Я читал книгу, в которой говорится, что сложность времени внешних циклов равна 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);
}

0

Решение

Цикл 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
0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector