时间戳

首页 > 解决方案 > 我不明白这个算法的时间复杂度是如何计算的

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

问题描述

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)？

标签： calgorithmloopstime-complexitybig-o

解决方案

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

很明显，循环体重复了n次，因为我们设置为，并在 时停止，并且每次迭代我们递增。forii=0i >= Ni

现在取决于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 ) .

推荐阅读