確定時間複雜

Question

我正在看書它告訴外部環路的時間複雜度是O（納米），而對於內環書給出解釋

「內的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); 
} 

Answer 1

while循環：？

while ((j<m) && (t[i+j]==p[j])) 
     j = j+1; 

爲O（M），那麼你必須從+2（other statements）：

j=0;      // + 1 
    // loop 
    if (j == m) return(i); // + 1