下面的嵌套循環代碼的時間複雜度是多少？

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

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

下面的嵌套循環代碼的時間複雜度是多少？

回答

相關問題