2

次の疑似コードの実行時間を分析するのを手伝ってくれる人はいますか

for(i = 0; i < n*n*n; i++)
    for(j = i; j < n; j++)
        x++

私が見る方法は、下限の omega(n^3) です。これは、外側の for ループ内がちょうど theta(1) である場合にそうなるからです。

外側のループの最初の n 回だけ実行される内側のループに混乱しています。内部ループの実行時間を平均するだけですか: n^3 * ((1/n^2)*n + (1/n)*1、この場合は O(n^3) ですか?

4

3 に答える 3

2

コンパイラがどれほど賢いかによって異なります。アルゴリズムは 2 つの部分に分けることができます (これは 1 つのエラーによってずれている可能性がありますが、アイデアは得られます)。

// i<n
// O(n^2)
for( i=0; i<n ; ++i )
  for( j=i; j<n; ++j )
    x++

// n < i < n*n*n
// O(n^3)
for( i=n ; i<n*n*n; ++j)
  noop(); //do nothing

2 番目の部分は何i > nもしないため、スマート コンパイラは i を n にループするだけで、その場合は O(n^2) になります。

ただし、コンパイラが賢くない場合、後半も実行され、O(1) 比較が得られるだけなので、全体的な動作は O(n^3) になります。

于 2011-11-03T01:45:26.647 に答える
1

内側のループは次の場合にのみ実行されますi<n。そうですO(n^2)。

于 2011-11-03T01:44:54.923 に答える
0

アルゴリズムは次のように分析する必要があります。

for(i = 0; i < n*n*n; i++) {
    for(j = i; j < n; j++) {
        x++
    }
    if (i >= n) {
        y ++;
    }
}

Wherexは内側ループと外側ループの両方の数を計算しy、内側のループが実行されなくなったときに外側のループの反復回数を計算します。

したがって、正式には次のように進めることができます。

ここに画像の説明を入力

の場合n = 10、結果は x = 55、y = 990 となり、上記の式と互換性があります。

于 2014-04-12T16:56:16.450 に答える