嵌套循环的大O符号[重复]

Question

for (int i = 0; i < N; i++){
    for (int j = 0; j < N; j++){
       do something;
    }
}

for (int i = 0; i < 1000; i++){
    for (int j = 0; j < N; j++){
        do something;
    }
}

Answer 1

你的第一个说法是正确的。N可以很大，O(N)将其考虑在内。

所以第一个代码是O(N^2)而第二个代码是O(1000*N)=>仍然是O(N)

大O表示法不包括常量