Java 3個log（n）嵌套循環的Big O表示法

大O表示法對於下面的嵌套循環會有什麼作用？Java 3個log（n）嵌套循環的Big O表示法

 for (int i = n; i > 0; i = i/2){ 
     for (int j = n; j > 0; j = j/2){ 
      for (int k = n; k > 0; k = k/2){ 
       count++; 
      } 
     } 
    }

我的想法是：每個迴路是O(log2(n))因此，它是那樣簡單乘法

O(log2(n)) * O(log2(n)) * O(log2(n)) = O(log2(n)^3)

來源

2013-01-23 Kailua Bum

我的假設也將是'O（LOG 2（N）^ 3）'。 –

是的，這是正確的。

找出嵌套循環的大O複雜性的一種方法，其邊界不會立即相互依賴，這是從內到外的工作。最內層的循環做O（log n）工作。第二個循環運行O（log n）次，並且O（log n）每次都工作，所以它會執行O（log n）的工作。最後，最外面的循環運行O（log n）次，並且O（日誌 n）在每次迭代中工作，因此完成的總工作是O（日誌 n）。

希望這會有所幫助！

來源

2013-01-23 06:29:19 templatetypedef

什麼是正確的符號？ O（log2（n）^ 3）或者你擁有它的方式？還是他們都可以接受？ –

我看過這兩種寫法。我個人喜歡用sin^2 x的形式登錄^ 3 n，儘管用上下文中使用的任何約定。 – templatetypedef

好的謝謝！ will do –

是的你是對的。

簡單的方法來計算 -

for(int i=0; i<n;i++){ // n times 
    for(int j=0; j<n;j++){ // n times 
    } 
}

簡單的嵌套循環的這個例子。這裏每個循環O（n）的Big-O是嵌套的，因此通常是O（n * 2），即O（n^2）實際的Big-O。而在你的情況 -

for (int i = n; i > 0; i = i/2){ // log(n) 
    for (int j = n; j > 0; j = j/2){ // log(n) 
     for (int k = n; k > 0; k = k/2){ // log(n) 
      count++; 
     } 
    } 
}

這是嵌套循環，每個循環大O是O(log(n))這樣一起復雜性將是O(log(n)^3)

來源

2013-01-23 06:38:10

事實上，你的假設是正確的。您可以有條不紊地顯示它類似如下：

enter image description here

來源

2014-04-05 00:49:15

Java 3個log（n）嵌套循環的Big O表示法

回答

相關問題