嵌套循环的大O，有不同的迭代？

我在计算迭代依赖于外部循环的两组代码示例的Big O运行时遇到了一些麻烦。我对Big O运行时间有了基本的了解，并且我可以计算出更简单的代码示例的运行时间。我不太确定某些线路是如何影响运行时间的。嵌套循环的大O，有不同的迭代？

我会考虑这第一个O（n^2）。但是，我不确定。

for(i = 1; i < n; i++){ 
for(j = 1000/i; j > 0; j--){ <--Not sure if this is still O(n) 
    arr[j]++; /* THIS LINE */ 
} 
}

我对这个有点失落。 O（n^3）可能是O（n^2）？

for(i = 0; i < n; i++){ 
for(j = i; j < n; j++){ 
    while(j<n){ 
     arr[i] += arr[j]; /* THIS LINE */ 
     j++; 
    } 
} 
}

我发现这个职位和我申请这第一个代码示例，但我仍然不能确定第二。 What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?

来源

2017-07-26 below_avg_st

对于第二个循环（看起来你仍然需要一个答案），你有一些令人误解的代码，在那里你有3个嵌套循环，所以乍一看，它是有意义的运行时是O（n^3）。

但是，这是不正确的。这是因为最内层的while循环会修改j，这与for循环修改的变量相同。这段代码实际上相当于该位的代码如下：

for(i = 0; i < n; i++){ 
    for(j = i; j < n; j++){ 
    arr[i] += arr[j]; /* THIS LINE */ 
    j++; 
    } 
}

这是因为在里面while循环运行，增加Ĵ直到Ĵ== n，那么它打破了。此时，inner for循环将再次递增j并将其与n进行比较，在那里它会找到j> = n并退出。您应该已经熟悉这个案例，并将其识别为O（n^2）。

只需要注意，代码的第二位并不安全（技术上），因为当while循环结束运行后，如果您增加一个额外时间，j可能会溢出。这会导致for循环永远运行。但是，这只会在n = int_max（）时发生。

来源

2017-07-26 01:50:52 UnknowableIneffable

关于第一个。这是不是O(n^2) !!!为了简化和可读性起见，让我们把它改写在伪码的形式：现在

for i in [1, 2, ... n]:        # outer loop 
    for j in [1, 2, ... 1000/i]:      # inner loop 
     do domething with time complexity O(1).  # constant-time operation

，恒定时操作的内侧环路（其依赖于外环的参数i）内的数目可以是表现为：

现在，我们可以计算出恒定时操作的总体数量：

这里，N(n)是谐波数（见wikipedia），并有一个非常有趣的，这些数字财产：

哪里C是Euler–Mascheroni constant。因此，所述第一算法的复杂度是：

关于第二个。看起来好像代码中包含错误，或者它是一个技巧性测试问题。该代码解析为

for (i = 1; i < n; i++) 
    for(j = i; j < n; j++){ 
     arr[j]++; 
     j++; 
    }

内环采用

操作，因此我们可以计算出总的复杂性：因为它可以解决

来源

2017-07-26 02:18:50 FalconUA

这应该是公认的答案OP对问题1的错误回答。 – meowgoesthedog

@meowgoesthedog同意 – UnknowableIneffable

嵌套循环的大O，有不同的迭代？

回答

相关问题