嵌套的for循环和单个的for循环的Big O表示法 [英] Big O notation with nested for loops and single for loop

问题描述

    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.

这篇关于嵌套的for循环和单个的for循环的Big O表示法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！