for-loop - 嵌套和顺序 for 循环复杂度

Question

我正在做一些非常接近这段代码的事情：

for(int k=0; k<n; k++) {            // n
    for(int a=0; a<k; a++) {        // n/2 -> n (watch the a<k)
        ...                         // c
    }
    for(int i=0; i<n; i++) {        // n
        for(int a=0; a<i; a++) {    // n/2 -> n (watch the a<i)
            ...                     // c
        }
        for(int j=0; j<n; j++) {    //n
            ...                     //c
        }
    }
}

我试图找出的是复杂性......我发现了 O(n^3) 但我不想“接受”这个答案。基本上如果我删除 2 for(a) 循环，它会是相同的复杂性？

但实际上这些代码不会有相同的执行时间，可能不会那么接近..为什么它仍然是 O(n^3) ：/

Answer 1

删除 for(a) 后，它仍然是 O(n^3)。

https://www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity

此外，带有嵌套 for 循环和单个 for 循环的 Big O 表示法