给定c ++代码的时间复杂度是多少？

Question

代码片段的时间复杂度是多少？

for ( i = 0; i < N * N; i += N )
k++;

我不确定是N ^ 2还是N，因为在每个循环中i都加了N。

Answer 1

上述程序的复杂度为O（n），因为只有一个'for'循环。

'for'循环的嵌套顺序提供了对最坏情况复杂度的粗略估计。

（（有关更多信息，请参阅下面的Cigien评论）

最坏情况复杂度的粗略估计：

如果有两个for循环，一个循环嵌套在另一个循环内，则复杂度可能变为o（n ^ 2）。

如果有3个嵌套循环，则复杂度可能变为O（n ^ 3）

...

O（n ^ 2）复杂度的示例：

for ( i = 1; i < P ; i ++ ) {
    for ( j = 1; j < Q; j++ ) {
        // some simple statements only
    }
}

O（n ^ 3）复杂度的示例：

for ( i = 1; i < P ; i ++ ) {
    for ( j = 1; j < Q; j++ ) {
        for ( k = 1; k < R; k++ ) {
            // some simple statements only
        }
    }
}