时间戳

首页 > 解决方案 > 具有条件的 3 个嵌套循环的时间复杂度

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

问题描述

这个函数的时间复杂度（大 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;
}

标签： c++algorithmtime-complexitybig-o

解决方案

复杂度是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;
}

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) 
            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)（和j++，j<=i*i）O(n^3)时间，这使得整个算法O(n^3)

推荐阅读