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

Question

内部 while 循环将被调用 N 次，其中 j 最多递增 n 次，因此总共最多会递增 n^2 次，因此时间复杂度应该是 O(N^2)，这是正确的，但是 O(N ）对于这个算法也可以。

Answer 1

j 仅在第 1 行分配（分配零）。之后，第 j 行仅在第 4 行被触摸，才会递增。

像这样，在最坏的情况下，在 for 循环的第一次迭代中，当

i = 0

和

A[i] - A[j] > D

始终评估为 true 时，j 将递增，直到达到 N。 之后，for 循环的其他迭代都将是 O(1)，因为内部 while 循环将永远不会被执行。

在算法的整个执行过程中，j递增不超过N次，就像你发来的解释说的那样。

Answer 2

这可以解决问题吗：

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