具有if语句的嵌套循环的时间复杂度O（N）：O（N ^ 4）？

问题描述

我试图找出这个片段的big-O的严格限制：

I am trying to figure out a tight bound in terms of big-O for this snippet:

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从1运行到i ^ 2，这将在m = {1,2，...，i}时发生，这意味着它将是真的i次，并且我最多可以是n，所以最坏的情况将是是m = {1,2，...，n} = n次。
如果i = n，第二个循环应该具有O（N ^ 2）的情况。
外环的最坏情况复杂度为O（N）。

If we start with the inner most loop, it will in worst case run k = n^2 times, which accounts for O(N^2).The if-statement will be true every time j = m*i, where m is an arbitrary constant. Since j runs from 1 to i^2, this will happen when m= {1, 2, ..., i}, which means it will be true i times, and i can at most be n, so the worst case will be m={1,2, ..., n} = n times. The second loop should have a worsts case of O(N^2) if i = n.The outer loop has a worst case complexity of O(N).

我认为这将以下列方式组合：内部循环的O（N ^ 2）*第二循环的O（N ^ 2）* O（ N）对于外部循环给出最坏情况时间复杂度O（N ^ 5）

I argue that this will combine in the following way: O(N^2) for the inner loop * O(N^2) for the second loop * O(N) for the outer loop gives a worst case time complexity of O(N^5)

然而，if语句保证我们只会到达内部循环n次，不是n ^ 2。但无论如何，我们仍然需要经历外循环n * n ^ 2次。 if-test是否会影响代码段的最坏情况时间复杂度？

However, the if-statement guarantees that we will only reach the inner loop n times, not n^2. But regardless of this, we still need to go through the outer loops n * n^2 times. Does the if-test influence the worst case time complexity for the snippet?

编辑：修正了j到i ^ 2，而不是i。

Corrected for j to i^2, not i.

推荐答案

您可以通过重写循环来简化分析，而不需要，如果 ，如下：

You can simplify the analysis by rewriting your loops without an if, as follows:

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 ）。

This eliminates steps in which the conditional skips over the "payload" of the loop. The complexity of this equivalent system of loops is O(n).

这篇关于具有if语句的嵌套循环的时间复杂度O（N）：O（N ^ 4）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！