0

私は、外側のループの時間計算量がO（nm）であると述べている本を読んでいましたが、内側のループの場合、本は次のように説明しています。

「内側のwhileループは最大でm回周回し、パターンマッチが失敗した場合ははるかに少なくなる可能性があります。これに加えて、他の2つのステートメントは、外側のforループ内にあります。外側のループは最大でn-m回周回します。テキストの右側に移動しすぎると、完全な位置合わせが可能になります。ネストされたループの時間計算量は倍増するため、最悪の場合の実行時間はO（（n − m）（m + 2））になります。 "

内部ループの時間計算量がO（m）ではなくO（m + 2）である理由がわかりませんでしたか？助けてください。

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);
}
4

1 に答える 1

0

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
于 2012-12-27T05:18:30.783 に答える