5

コンピュータ サイエンス II のファイナルは明日です。コード セグメントのビッグ オーを見つける方法を理解するための助けが必要です。私はインターネットを検索しましたが、どのように理解する必要があるかの例を見つけることができませんでした.

以下は、サンプルファイナルの問題です。

for(int pass = 1; i <= n; pass++)
{
    for(int index = 0; index < n; index++) 
        for(int count = 1; count < n; count++) 
        {
            //O(1) things here.
        }
    }
}

アルゴリズムの順序 (Big-Oh) を見つけることになっています。

O(n^3) になると思いますが、その結論に至った経緯は次のとおりです。

for(int pass = 1; i <= n; pass++) // Evaluates n times
{
    for(int index = 0; index < n; index++) // Evaluates n * (n+1) times
        for(int count = 1; count < n; count++) // Evaluates n * n * (n) times
        {
            //O(1) things here. 
        }
    }
}
// T(n) = (n) + (n^2 + n) + n^3
// T(n) = n^3 + n^2 + 2n
// T(n) <= c*f(x)
// n^3 + n^2 + 2n <= c * (n^3)
// O(n) = n^3

私はそれを正しく行っているかどうかわかりません。誰かがこのようなコードを評価する方法を説明したり、私の答えを確認したりできますか?

4

2 に答える 2

0

あなたは絶対に正しいです。あなたの例では O(n^3) です。

コードの任意のセグメントの Big Oh 実行時間を見つけるには、コードの一部が O(1) のことを何回実行するかを考える必要があります。

これをよりよく理解するために、例を単純化してみましょう。

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times
    for(int count = 1; count < n; count++) // Evaluates n * n * (n) times
    {
        //O(1) things here. 
    }
}

上記の場合、内側のループは、外側のループの実行ごとに n 回実行されます。また、外側のループも n 回実行されます。これは、n 回、n 回実行していることを意味します。O(n^2)にする。

もう 1 つ気を付けなければならないことは、Big Oh が上限であるということです。これは、入力が大きい場合 (この場合、 の値が大きい場合) にコードに何が起こるかを常に考える必要があることを意味しますn。この事実のもう 1 つの意味は、定数を掛けたり足したりしても Big Oh以下に例を示します。

for(int index = 0; index < n; index++) // Evaluates n * (n+1) times
    for(int count = 1; count < 2*n; count++) // Runs 2*n times
    {
        //O(1) things here. 
    }
}

O(n*(2n)) = O(n^2) であるため、このコードの Big Oh 実行時間も O(n^2) です。

これもチェックしてください：http://ellard.org/dan/www/Q-97/HTML/root/node7.html

于 2013-05-05T22:40:26.310 に答える