具有条件的 3 个嵌套循环的时间复杂度

Question

这个函数的时间复杂度（大O）是多少？以及如何计算它？

我认为是 O(N^3)，但不确定。

int DAA(int n){
    int i, j, k, x = 0;
    for(i=1; i <= n; i++){
        for(j=1; j <= i*i; j++){
            if(j % i == 0){
                for(k=1; k <= j; k++){
                    x += 10;
                }
            }
        }
    }
    return x;
}

Answer 1

如果摆脱无所事事的迭代，时间复杂度可以更容易计算。除非 j 是 i 的倍数，否则中间循环不执行任何操作。所以我们可以强制 j 是 i 的倍数并去掉 if 语句，这样代码更容易分析。

int DAA(int n){
    int x = 0;
    for(int i=1; i <= n; i++){
        for(int m=1; m <= i; m++){  // New variable to avoid the if statement
            int j = m*i;            // The values for which the inner loop executes
            for(int k=1; k <= j; k++){
                x += 10;
            }
        }
    }
    return x;
}

外循环迭代n次。到目前为止 O(n)。

中间循环迭代 1 次，然后 2 次，然后... n 次。人们可能会从 O(n²) 排序算法中认出这一设置。循环执行n次，迭代次数增加到n，导致O(n×n)复杂度。

内层循环执行n×n次（中间循环的复杂度）。每次执行的迭代次数增加到n×n（j的最大值）。类似于中间循环如何将其执行次数和最大迭代次数相乘以获得其复杂性，内部循环的复杂性——因此整个代码的复杂性——应该变为 O(n⁴), 但我会把精确的证明留作练习。

上面确实假设时间复杂度表示x += 10;执行的次数。也就是说，它假设最内层循环的主要工作压倒了其余的工作。这通常是我们感兴趣的内容，但也有一些注意事项。

首先要注意的是，添加 10 并不比递增更多的工作。如果行 x += 10; 不是“做工作”的方便替代，那么时间复杂度可能应该包括所有迭代，即使是那些不工作的迭代。

第二个注意事项是 if 语句中的条件相对于最内层循环而言成本较低。在某些情况下，条件可能很昂贵，因此时间复杂度应包括执行 if 语句的次数。删除 if 语句确实会干扰这一点。

如果您碰巧遇到这些警告之一，您将需要计算遗漏的内容。修改后的代码省略了中间循环的 i²−i 次迭代，每次 n 执行。因此，省略的迭代将对整体复杂度产生 n 次 n²−n，或 O(n³)。

因此，原码的复杂度为O(n⁴ + n³)，与O( n⁴).

Answer 2

复杂度为O(n^4)

但这不是因为你盲目地放弃未使用的迭代。

这是因为当你考虑所有指令时，O(n + n^3 + n^4) = O(n^4)

int DAA(int n){
   int x = 0;
   for(int i=1; i <= n; i++) // O(n)
      for(int j=1; j <= i*i; j++) // O(1+2+...n^2) = O(n^3)
         if(j % i == 0) // O(n^3) same as loop j
            for(int k=1; k <= j; k++) // O(n^4), see below
               x += 10; // O(n^4) same as loop k

   return x;
}

条件内循环的复杂度

循环k仅在j%i==0时执行，即{i, i*2, i*3 ... i*i}

所以对于最内层循环执行的情况，算法是有效的

int DAA(int n){
   int x = 0;
   for(int i=1; i <= n; i++) // O(n)
      for(int t=1; t <= i; t++) // O(1+2+...+n) = O(n^2)
         for(int k=1; k <= t*i; k++) // O(n^4)
               x += 10;
   return x;
}

为什么简单地删除未使用的迭代不起作用？

假设现在

int DAA(int n){
   int x = 0;
   for(int i=1; i <= n; i++) // O(n)
      for(int j=1; j <= i*i; j++) // O(1+2+...+n^2) = O(n^3)
         if(j == i) 
            for(int k=1; k <= j; k++)
               x += 10; // oops! this only run O(n^2) time

   return x;
}
// if(j==i*log(n)) also cause loop k becomes O((n^2)log(n))
// or, well, if(false) :P

虽然最里面的指令只有运行O(n^2)次。该程序实际上执行 if(j==i)(and j++, j<=i*i) O(n^3) 时间，这使得整个算法 O(n^3)

具有条件的 3 个嵌套循环的时间复杂度

Time complexity of 3 nested loops with a condition

c++

algorithm

big-o

time-complexity

条件内循环的复杂度

为什么简单地删除未使用的迭代不起作用？