确定时间复杂

我正在看书它告诉外部环路的时间复杂度是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); 
}

来源

2012-12-27 zukes

为什么会这样塔格ed C++？我们确定这个代码是C++（可能是C）。作业标签（我们不应该使用）可能实际上会更好.... – debracey

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

来源

2012-12-27 05:18:30 perreal

那么为什么我们还没有给外部循环中的j = 0 O（1），还是我们不说O（ 1）初始化语句？谢谢你的回应。 – zukes

确定时间复杂

回答

相关问题