c - 我不明白这个算法的时间复杂度是如何计算的

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 的正文循环重复 n 次，因为我们设置了 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)。