下面的嵌套循环代码的时间复杂度是多少？

for(i=n/2;i<=n;i++) { 
    for(j=1;j<= n/2;j++) { 
     for(k=1;k<=n;k=k*2) { 
      statement; 
     } 
    } 
}

该代码的复杂性是什么，我认为它会记录n^2，但我找不到它，请回答我。下面的嵌套循环代码的时间复杂度是多少？

来源

2016-07-29 bhagyashri kshirsagar

的可能的复制[如何找到时间算法的复杂度（http://stackoverflow.com/questions/11032015/how-找到时间复杂度的算法） –

for(i=n/2;i<=n;i++) {   // it is O(n) 
    for(j=1;j<= n/2;j++) { // it is O(n) 
     for(k=1;k<=n;k=k*2) { // it is O(log n) 
      statement; 
     } 
    } 
}

因此为O（n^2 *（log n）的）

来源

2016-07-29 16:33:50 dmitry

我不明白log n是怎么来的，你能解释一下吗？ –

长答案你可以找到，例如，在这里http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly?rq=1 简而言之，这里的复杂性是log2 n。因此，如果n增长8倍，则需要（log2 8）更多时间（仅在最后一个循环中），即计算需要多3倍。 – dmitry

好的..非常感谢你.. –

下面的嵌套循环代码的时间复杂度是多少？

回答

相关问题