-1 
for (int i=0; i<N; i++)
 for (int j=i; j<N; j++)
  fun1(i,j);

上記はネストされた for ループです。最初の for ループは 0 から N まで進み、2 番目の for ループは i から N まで進みます。上記のコードの時間計算量はどれくらいですか?

編集: fun1 は o(1)

4

5 に答える 5

5

O(n²*O(楽しい))。明らかに、答えは楽しみの複雑さに依存します。

編集: fun() = O(1) であるため、複雑さのループの複雑さは O(n²) です。

于 2012-06-12T16:36:19.363 に答える
2

ループ回数は 1+2+3+...+N = N * (N + 1)/2 = N^2/2 + N/2 です。したがって、時間計算量は O(N^2/2 + N/2) = O(N^2) です。

于 2012-06-12T16:46:06.607 に答える
1

外側の for ループは、内側の for ループを N 回実行します。

内側の for ループは、外側のループの最初のサイクルで fun1(i,j) を N 回呼び出します。次に、外側の for ループの 2 番目のサイクルで (N-1) 回。次に、(N-2) 回、次に (N-3) 回というように、fun1(i,j) が 1 回だけ実行されるとき、外側のループの N 番目のサイクル (i = N-1) まで続きます。そのため、内部ループの反復ごとに平均 N/2 回 fun1(i,j) を実行しています。

したがって、fun1(i,j) の複雑さが O(fun1(i,j)) であると仮定すると、全体の複雑さは O(n * (n/2) * O(fun1(i,j))) = O( n^2/2 * O(fun1(i,j))) しかし、複雑さを測定するために N の大きな値の数値定数を無視できるため、コードの複雑さの順序はO(n^2 * O(fun1( i,j)))

fun1(i,j) は一定時間O(fun1(i,j)) = O(1) なので、コードの複雑さはO(n^2)になります

同様の例は、このSelection Sort Algoで見ることができます。選択ソート アルゴリズムを参照してください。ここでは、fun1(i,j) の代わりに単純な割り当て行 'index_of_min = y;' を使用します。が使用されていますが、これはあなたの例に似ており、役立つ場合があります。

于 2012-06-12T16:54:01.790 に答える
1

fun1()は一定時間な ので、ループの複雑さはO(N^2)

于 2012-06-12T16:40:27.823 に答える
0

内側のループの本体は時間を実行しN + (N - 1) + (N - 2) + ... + 3 + 2 + 1ます

したがって、N + (N - 1) + (N - 2) + ... + 3 + 2 + 1 <= N * Nループの本体は、成長する回数実行されますO(n^2)

コードの総時間の増加は、 の複雑さに依存しますfun1 ()。fun1 ()時間の増加がある場合O(fun1)、fun1 ()実行されるO(N^2)回数は次のようになります。O(n^2 * O (fun1 ()))

編集

fun1 ()あなたが編集したO(1)ように、全体の複雑さはO(n^2 * O (fun1 ())) = O(n^2)

于 2012-06-12T16:36:42.433 に答える