c - 当有两个独立的 for 循环时如何找到大 O

Question

我知道如何找到“for 循环”和嵌套“for 循环”的 Big O，但是当我们有两个 for 循环时会发生什么，不是嵌套而是在同一个函数中有两个单独的 for 循环。

Answer 1

它只是被添加。

参见例如:

for(i=0;i<n;i++)
    //statements

for(i=0;i<m;i++)
    //statements

所以总的复杂度是 O(m+n)。

然后假设 m=3n它的 O(4n) 只有 O(n)。

令 m = n^2

然后它的 O(n^2+n) 即 O(n^2)