这个算法的时间复杂度怎么可能是 O(N) 呢？

Question

我得到这段代码的来源声称它的时间复杂度是 O(N)，但这怎么可能呢？在我看来，时间复杂度应该是 O(N ² )。

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

内部 while 循环将被调用Ntimes，j最多递增2N次，因此总共最多递增N²次。因此，时间复杂度应该是O( N² )。N这个算法怎么可能 O( ) 也可以呢？

Answer 1

j 仅在第 1 行分配（分配零）。之后，仅在第 4 行处触及第 j 行，即可递增。

像这样，在最坏的情况下，在 for 循环的第一次迭代中，当i = 0和 A[i] - A[j] > D始终计算为 true 时，j 将递增，直到达到 N。之后，for 循环的其他迭代都将是 O(1) 因为内部 while 循环永远不会被执行。

在算法的整个执行过程中，j 的增量不超过 N 次，就像您发送的解释所述。