2

だから、私はビッグオー表記を本当に取得しません。私は、このコード セグメントの「O 値」を決定する任務を負っています。 

for (int count =1; count < n; count++) // Runs n times, so linear, or O(N)
    { 
        int count2 = 1;        // Declares an integer, so constant, O(1)

        while (count2 < count) // Here's where I get confused. I recognize that it is a nested loop, but does that make it O(N^2)?
            {
                count2 = count2 * 2;   // I would expect this to be constant as well, O(N)
            }
    }
4

1 に答える 1

2 
O(f(n))=g(n)

これは、ある値k、f(n)>g(n)どこでn>k. これにより、関数 の上限が得られますg(n)。

Big Oコードを探すように言われたら、

1) によって実行される計算の数を数えてみてください。nしたがって、 が得られg(n)ます。

2) の上限関数を推定してみてくださいg(n)。それがあなたの答えになります。

この手順をコードに適用してみましょう。

行われた計算の数を数えましょう。ステートメントdeclaringと時間multiply by 2がかかりO(1)ます。しかし、これらは繰り返し実行されます。それらが実行された回数を見つける必要があります。

外側のループはn回実行されます。したがって、最初のステートメントはn回実行されます。内側のループが実行される回数は、 の値に依存しますn。指定された値に対して、nそれは何回も実行されlognます。

実行された計算の総数を数えましょう。

log(1) + log(2) + log(3) +.... log(n) + n

最後nは最初のステートメントであることに注意してください。上記のシリーズを単純化すると、次のようになります。

= log(1*2*3*...n) + n

= log(n!) + n

我々は持っています

g(n)=log(n!) + n

の上限を推測してみましょうlog(n!)。

以来、

1.2.3.4...n < n.n.n...(n times)

したがって、

log(n!) < log(n^n) for n>1

これは意味する

log(n!) = O(nlogn).

正式な証明が必要な場合は、こちらを参照してください。nlognより速く増加するため、n次のようになります。

O(nlogn + n) = O(nlogn)

したがって、最終的な答えはO(nlogn)です。

于 2013-10-19T03:52:27.527 に答える