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

Question

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

考虑这个代码 -

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