0

私は大きな O 表記に関するフォーラムを検索しており、かなりのことを学びました。私の問題はかなり具体的であり、ユニークなケースが大きな O を理解するのに役立つと思います。定数は無視しています。

私の理解では、ループが O(n) よりもすべての要素を通過する場合。

for(int i = 0; i < n; i++)
{   

}

ループが n のすべてを通過する場合、n のすべてを通過する別のループ内では、n * n = n^2 が乗算されます。

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

    }
}

最後に、ループの後にすべての要素を通過する別のループが続く場合、n + n = 2n です。

for(int j = 0; j < n; j++)
{

}
for(int k = 0; k < n; k++)
{

}

私の質問は、これらのコード行に直接進みます

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

    }
    for(int k = 0; k < n; k++)
    {

    }
    for(int l = 0; l < n; l++)
    {
        for(int m = 0; m < n; m++)
        {

        }
    }

}

したがって、上記のルールに基づいて、大きな O が n * (n + n + n * n)、つまり n^3 + 2n^2 になるように計算しています。それで、それは私の大きなO（n ^ 3）になりますか、それとも私の大きなOはO（n ^ 3 + 2n ^ 2）になります。私はこれについてすべて間違っていますか？それとも私は球場の近くにいますか？主に、これらのループが O(n^4) 未満になるかどうかを調べようとしています。前もって感謝します。

4

1 に答える 1

2

big-O 表記法は、データ量を示す値 n に応じてアルゴリズムの漸近動作を特徴付けるために使用されますが、プロセッサ速度などの定数には依存しません。
あなたの例では、n^3 は 2n^2 よりも速く成長しました。つまり、n が大きい場合、2n^2 は n^3 と比較して無視できます。したがって、ネストされたループの漸近動作の順序は O(n^3) です。

于 2013-04-03T05:05:58.877 に答える