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时都为真，其中m是一个任意常数。由于j从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

    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)

Answer 2

您可以通过在不使用if的情况下重写循环来简化分析，如下所示：

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

这消除了条件跳过循环“有效载荷”的步骤。这个等价循环系统的复杂度是O（n⁴）。