6

次の入れ子になったループの 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)
4

3 に答える 3

11

はい、そうです。

入れ子になったループの境界がすぐには相互に依存しないという大きな複雑さを理解する 1 つの方法は、内側から外側に向かって作業することです。最も内側のループは O(log n) の作業を行います。2 番目のループは O(log n) 回実行され、毎回 O(log n) の作業が行われるため、O(log 2 n) の作業が行われます。最後に、最も外側のループは O(log n) 回実行され、各反復で O(log 2 n) の作業が行われるため、実行される作業の合計は O(log 3 n) になります。

お役に立てれば！

于 2013-01-23T06:29:19.927 に答える
1

はい、その通りです。

計算する簡単な方法-

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

この単純なネストされたループの例。ここでは、各ループO（n）のBig-Oがネストされているため、通常はO（n * n）であり、これは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++;
         }
     }
}

これはネストされたループにあり、各ループはBig-OであるO(log(n))ため、複雑さはすべて一緒になりますO(log(n)^3)

于 2013-01-23T06:38:10.657 に答える