c++ - 确定时间复杂度

Question

我正在读一本书，它告诉外循环时间复杂度是 O(nm) 而对于内循环，这些书给出了解释

" 内部 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)，那么你从 ( other statements) 得到 +2：

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