嵌套的for循环和单个的for循环的Big O表示法

本文介绍了嵌套的for循环和单个的for循环的Big O表示法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 int a = 0, b = 0; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { a = a + j; } } for (k = 0; k < N; k++) { b = b + k; }

我正在尝试计算上述时间的复杂性.

I am trying to work out the time complexity of the above.

我当时以为是O(n^2 + n)我的理由是:

I was thinking it was O(n^2 + n) my reasoning is:

n^2 : nested for loops n : Adding the single loop

但是，确认的答案是O(n^2)

我的问题是，为什么要包含最后一个for循环，因为它本身就是O(n)

My questions is why is the last for loop included as that on its own would be O(n)

非常感谢您的任何建议，

Many thanks for any suggestions,

推荐答案

使用Big-O表示法，您可以获取最高阶的成分并删除其他乘法因子.原因是，随着"n"在指数过程中变大，添加另一个"n"并不会真正改变它.

With Big-O notation you take the highest-order component and drop other multiplication factors. The reason is that as "n" gets larger in an exponential process, adding another "n" doesn't really change it much.

如果n=1000000，则n^2为1000000000000.用+ n表示为10000001000000并没有太大的影响.随着n变大，影响甚至可以忽略不计.

If n=1000000 then n^2 is 1000000000000. Saying + n to make it 10000001000000 doesn't have a significant impact. As n grows larger, the impact is even more negligible.

对于n log n之类的东西，反之亦然，因为您要增加一个数量级，因此保持该乘数会产生相当大的影响.

The inverse is true for something like n log n where you're increasing by an order of magnitude, so keeping that multiplication factor has an appreciable impact.