我不明白如何计算此算法的时间复杂度

Question

int j=0;
for (int i=0; i<N; i++) 
{
    while ( (j<N-1) && (A[i]-A[j] > D) )
        j++;
    if (A[i]-A[j] == D) 
        return 1; 
}

据说这段代码的时间复杂度为O(n),但我并没有真正得到它.内循环执行N次,外部也应该N次？是因为j = 0; 在循环之外使它只运行N次？

但即使它只在内循环中运行N次,if语句检查也应该进行N次,这应该将总时间复杂度带到O(n ^ 2)？

Answer 1

这是O(n)的原因j是因为没有回到循环0体中for.

事实上,如果我们看一下for循环体,我们会看到:

while ( (j<N-1) && (A[i]-A[j] > D) )
    j++;

因此,这意味着j++最多完成n-1次,因为如果j成功的N-1次数,则第一个约束失败.

如果我们看一下整个for循环,我们会看到:

int j=0;
for (int i=0; i<N; i++) {
    while ( (j<N-1) && (A[i]-A[j] > D) )
        j++;
    if (A[i]-A[j] == D) 
        return 1;
}

很显然,在身体中的for循环重复ñ时间,因为我们设置i到i=0,停止的时候i >= N,每次我们增加迭代i.

现在取决于A我们将j在for循环体中增加(多次)的值.但无论在一次迭代中完成多少次,在for循环j++结束时,最多完成n次,原因我们在上面提到过.

while循环中的条件也执行O(n)(最多精确2×n-1次)次数:每次进入for循环体时执行一次,每次执行后执行一次一个j++命令,但因为两者都是O(n),所以这最多是O(n + n),因此是O(n)次.

循环中的if条件for执行n次:每次迭代for循环一次,所以再次执行O(n).

因此,这确实意味着,所有的"基本指令"( ,j++,i = 0,j = 0,j < N-1等等)都做任一个恒定的次数O(1) ,或次线性数目为O(n) ,因此该算法是为O(n ).