algorithm - 对同一个输入数组运行两次循环的复杂性是多少？

Question

我是算法的新手，对学习和实现它们非常感兴趣。
通过我能找到的所有可用的在线 Material 来学习它们。 我对此有点困惑 -

考虑这段代码-

for (int i=0; i<n; i++) { ..... }
for (int i=0; i<n; i++) { ..... }

这个的复杂度是多少？
O(n) 或 O(n^2)？

Answer 1

假设 { 。 . . 是常数时间，那么一次循环的复杂度是O(n)。

两个“相邻”循环的复杂度是多少？它是 O(n) + O(n)。或者您可以将其视为 O(n + n) --> O(2n)。常量从复杂性中剔除，所以这是 O(n)。

嵌套循环是完全不同的事情。所以如下:

for (int i=0; i<n; i++) { ..... }
    for (int j=0; j<n; j++) { ..... }

将是 O(n^2)。