如何计算以下函数的时间复杂度？

以下函数的时间复杂度是多少？如何计算以下函数的时间复杂度？

void function(int n){ 
     for(int i=0; i<n; i++){. //n times 
      for(int j=i ; j< i*i; j++){ // n*n times 
       if(j%i == 0){ 
        for(int k=0; k<j; k++){ // j times = n * n times. 
         ++counter; 
        } 
       } 
      } 
     } 
    }

书说O(n^5)。但我不明白为什么书没有考虑到j%i。基于此，k循环确定。你能澄清吗？

来源

2017-02-20 Manoj

让我们考虑代码的一部分，其中u有疑问：

for(int j=i ; j< i*i; j++) 
{ 
    if(j%i == 0) 
     { 
       for(int p=0; p<j; p++){ 
       ++counter; 
     } 
     }

就让我们分析这部分代码。每i，每当j是i的倍数，即现在

i, 2i, 3i, .... i*i // upto i*i only,since j<i*i

，对于每一个j，里面复杂O(j)j%i==0将是真实的。

所以复杂度的这部分代码是：

所以，整体复杂度= O(n*n^3) = O(n^4)

来源

2017-02-20 16:43:10

谢谢。你建议所有3个循环将采取O（n^4）。我有点困惑。你能不能请上面的外环解释一下。 – Manoj

@Manoj我正在写另一个答案，以澄清事情。将需要几分钟 –

@Manoj：对于一个特定的我，内部循环（我提到的代码部分）复杂度是O（i^3），并且因为我将从0-n变化，复杂度等于O （N^4）。至少这就是我所得到的。你可以提到这本书吗？ –

事实上函数在时间为O（N^4）中，由于if条件每约有n个循环只发生一次。请参阅下面的精确分析。

void function (int n) { 
    for(int i=0; i<n; i++) { 
     // Runs a total of n times 
     for(int j=i; j< i*i; j++) { 
      // Runs a total of (n^3 - n)/3 = O(n^3) times 
      if(j%i == 0) { 
       // Runs a total of (n^2 - n)/2 = O(n^2) times 
       for(int k=0; k<j; k++) { 
        // Runs a total of (3n^4 - 10n^3 + 9n^2 - 2n)/24 = O(n^4) times 
        ++counter; 
       } 
      } 
     } 
    } 
}

来源

2017-02-20 18:15:26 Charles

谢谢，你是如何计算公式的？我跑n = 5，但（n^3 - n）/ 3不来。 – Manoj

@Manoj我相信，你可以使用Faulhaber公式的变体来得到确切的表达式。我使用了PARI/GP的'sumformal'命令。大O表达式更容易，但确切的表达式表明我所拥有的是紧密的。 – Charles

如何计算以下函数的时间复杂度？

回答

相关问题