6

宿題ですが、一般的な方法をお願いしています。

次のコードの最悪の場合の実行時間を計算します。

int sum = 0;
for (int i = 0; i*i < N; i++)
    for (int j = 0; j < i*i; j++)
        sum++;

答えはN^3/2です、誰かがこれを通して私を助けることができますか？

これを計算する一般的な方法はありますか？

This is what I thought:

when i = 0, sum++ will be called 0 time
when i = 1, sum++ will be called 1 time
when i = 2, sum++ will be called 4 times
...
when i = i, sum++ will be called i^2 times

so the worst time will be
0 + 1 + 4 + 9 + 16 + ... + i^2

しかし、次は何？私はここで迷子になっています...

4

4 に答える 4

10

最も内側のサイクルが実行される回数をカウントする必要があります。

外側のものは、i=0からi=sqrt（N）まで実行されます（i * i <Nであるため）。外側の反復ごとに、内側の反復はi^2回実行されます。

したがって、内側のものが実行される合計回数は次のとおりです。

1^2 + 2^2 + 3^2 + ... + sqrt(N)^2

式があります：

1^2 + 2^2 + ... + k^2 = k(k+1)(2k+1) / 6 = O(k^3).

あなたの場合、k = sqrt（N）です。

これは全体の複雑さですO(sqrt(N)^3) = O(N^(3/2))。

于 2012-08-14T08:19:40.723 に答える
1

あなたは間違った方法でこの問題に取り組んでいます。最悪の時間をカウントするには、実行される操作の最大数を見つける必要があります。ダブルループには1つの操作しかないため、内側のループが何回実行されるかを知るだけで十分です。

これを行うには、ループの制限を調べます。外側のループの場合は次のとおりです。

i^2 < N => i < sqrt(N)

内側のループの制限は

j < i^2

2番目の式で代用してを取得できj < Nます。

これらはネストされたループであるため、制限を掛けて最終結果を取得します。

sqrt(N)*N = N^3/2
于 2012-08-14T08:24:26.367 に答える
1

アルゴリズムは次の形状に変換できます。

int sum = 0;
for (int i = 0; i < Math.sqrt(N); i++)
    for (int j = 0; j < i*i; j++)
        sum++;

したがって、次のことを簡単かつ正式に行うことができます。

ここに画像の説明を入力してください

于 2014-04-05T17:38:49.673 に答える
0

次に、この合計を計算します

（i ^ 2）/ 2 * N ^（1/2）= N / 2 * N ^（1/2）= N ^（3/2）

于 2012-08-14T08:19:39.077 に答える