具有if语句的嵌套循环的时间复杂度O(N):O(N ^ 4)?

我试图找出这个片段的big-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从1运行到i ^ 2,这将在m = {1,2,…,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 R个5)

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

编辑:更正了j到i ^ 2,而不是我。

您可以通过在没有if情况下重写循环来简化分析,如下所示:

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

这消除了条件跳过循环的“有效载荷”的步骤。 这个等效的循环系统的复杂性是O(n 4 )。

  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)