带有嵌套 for 循环和单个 for 循环的大 O 表示法

Question

    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;
    }

我正在尝试计算上面的时间复杂度。

我以为是 O(n^2 + n) 我的推理是：

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

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

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

非常感谢您的任何建议，

Answer 1

从技术上讲，运行时间为 O(n^2 + n) 是正确的，因为初始循环是二次循环，第二个循环是线性循环。然而，大 O 表示法的惯例是从大 O 表达式中删除常数因子和低阶项，因为大 O 表示法谈论长期限制行为。因此，O(n^2) 的给定答案是计算运行时的更好方法。您的答案在技术上并无不妥，但不被认为是好的数学风格。

Answer 2

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

如果 n=1000000 那么 n^2 就是 1000000000000。说 + n 变成 10000001000000 不会产生重大影响。随着 n 变大，影响就更微乎其微了。

反之亦然，例如 n log n，其中您增加了一个数量级，因此保持该乘数会产生明显的影响。

Answer 3

您无需提及 O(n)，因为与 O(n^2) 分类相比，它是微不足道的。当你的算法有一个 O(n) 部分和一个 O(1) 部分时，它的想法是一样的——你不称它为 O(n+1)，你称它为 O(n)。

这篇文章有很好的解释： https://www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity

Answer 4

第一组嵌套循环是 O(N^2)，第二组是 O(N)。这是 O(max(N^2,N)) 这是 O(N^2).

引用自：http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html >> 自我测试 #3

带有嵌套 for 循环和单个 for 循环的大 O 表示法

Big O notation with nested for loops and single for loop

big-o