0 
void mystery2 (int n)
{
 int i;
 for (i = 1; i <= n; i++) {
    double x = i;
    double delta = 1 / (double)i;
    while ( x > 0 )
      x -= delta;
  }
return 0;
}

推測ではなく、 http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html#applicationのような追跡テーブルを使用して、このプログラムの時間計算量を決定する方法は?

4

2 に答える 2

3

反復ごとに、最初は がありx=i、その後は毎回x減少します。1/iしたがって、これは何i/(1/i)==i^2度も繰り返されます。

したがって、 の反復ごとfor(i=1;i<n;++i)に、内部部分の複雑度は になりO(i^2)ます。iが 1 から n になると、 を足すようなもので、これ(1^2+2^2+3^2+...+n^2)はおおよそn^3/6です。したがって、それはO(n^3)です。

    Outer loop(for)          Inner Loop
    I=1                      1
    I=2                      4
    I=3                      9
    ...                      ..
    I=N                      N^2
 TOTAL_                      ~N^3/6
于 2013-02-28T15:50:26.793 に答える
2

これは比較的簡単です。ネストされた 2 つのループがそれぞれ何回実行されるかを判断し、複雑さを一緒に考慮する必要があります。

外側のループは自明なforループです。回実行nします。

内側のループにはもう少し注意が必要です。ゼロになるか負になるまで、1/iから減算し続けます。から減算するにはループの反復がi必要であることは簡単にわかります。は最初は に設定されているため、内側のループにかかる合計時間はです。iwhile1xxii^2

したがって、合計は との間のx2 乗の合計です。x1n

Wolfram Alpha によると、これに対する答えはn*(n+1)*(2n+1)/6

n^3/3 + n^2/2 +n/6これは の複雑さを持つ多項式に展開されO(n^3)ます。

于 2013-02-28T15:56:02.203 に答える