8

別の質問を読んでいたところ、このコードに興味をそそられました。

for(i = 0; i < n; i++)
{
    for(j = 0; j < i*i; j++)
    {
        for(k = 0; k < i*j; k++)
        {
            pseudo_inner_count++;
            for(l = 0; l < 10; l++);
        }
    }
}

これがどうして O(N^6) になるのかわかりません。誰かが私のためにそれを分解できますか?

4

3 に答える 3

15

実際には次のとおりです。

  • i ループは O(N) 回繰り返されるため、i の値は O(N) であり、O(I)=O(N) と言えます。
  • j ループは、O(I^2) = O(N^2) 回反復します (外側のループを除いて、単独で考えた場合)。
  • k ループは O(I*J) = O(N*N^2) = O(N^3) 回反復します。
  • l ループは 10 回繰り返すだけなので、O(1) になります。

ループはネストされているため、これらを乗算する必要があります (理由がわかりますか?)。合計は O(N)*O(N^2)*O(N^3) = O(N^6) です。

于 2011-07-21T04:57:05.817 に答える
1

これは

最初のループの場合は n 、2 番目のループの場合は n²、3 番目のループの場合は n³

内側のループは O(1)

合計は O(n⁶) です。

3 番目のループが n³ である理由は、考えてみると、j が n² に到達し、i が n に到達するため、i*j が n³ に到達するためです。

于 2011-07-21T04:57:48.223 に答える
-1

私は言うだろう：

  • 最初のループの n
  • 2 番目のループの n² => n³ の合計
  • 3 番目のループの n² => n⁵ の合計</li>
  • さらに別の n ループ => 合計 n⁶</li>
于 2011-07-21T04:44:06.307 に答える