带有 if 语句的嵌套循环的时间复杂度 O(N)：O(N^4)？

Question

我正试图找出这个片段的大 O 的严格界限：

for(int i = 1 ; i <= n ; i++) {
    for(int j = 1; j <= i*i ; j++) {
        if (j% i == 0){
            for(int k = 0 ; k<j ; k++ )
                sum++;
        }
    }
}

如果我们从最内层的循环开始，最坏的情况下它会运行 k = n^2 次，这占 O(N^2)。每次 j = m*i 时，if 语句都为真，其中 m 是任意常数。由于j运行s从1到i^2，当m={1, 2, ..., i}时会出现这种情况，也就是说i次为真，i最多为n次，所以最坏的情况是 m={1,2, ..., n} = n 次。如果 i = n，第二个循环应该有 O(N^2) 的最坏情况。外层循环的最坏情况复杂度为 O(N)。

我认为这将按以下方式组合：内部循环的 O(N^2) * 第二个循环的 O(N^2) * 外部循环的 O(N) 给出了最坏的情况O(N^5)

的时间复杂度

但是，if 语句保证我们只会进入内循环 n 次，而不是 n^2 次。但不管怎样，我们仍然需要经历n * n^2次外层循环。 if 测试是否会影响代码段的最坏情况时间复杂度？

编辑：将 j 更正为 i^2，而不是 i。

Answer 1

您可以通过重写没有 if 的循环来简化分析，如下所示：

for(int i = 1 ; i <= n ; i++) {
    for(int j = 1; j <= i ; j++) {
        for(int k = 0 ; k<j*i ; k++ ) {
            sum++;
        }
    }
}

这消除了条件跳过循环的 "payload" 的步骤。这个等效循环系统的复杂度是 O(n⁴).

Answer 2

    I analyse your question in a more straightfroward way
    we first start by fix i as a costant, 
    for example, assume it to be k,
    so j=1~k^2, when j=k,2k,3k,...,k^2, assume j to be c*k (c=1~k)
    the next loop will be executed c^2 times, 
    so the complexity for a fix i can be expressed as=>
    (1+.....+1)+(1+1+...+2^2)+(1+1+...+3^2)+.....+(1+1+...+k^2)
    = O(k^3)
    so now we set k to be 1~n, so the total complexity will be O(n^4)

带有 if 语句的嵌套循环的时间复杂度 O(N)：O(N^4)？

Time complexity O(N) of nested loops with if-statement: O(N^4)?

java

big-o

time-complexity

nested-loops