-1

Fizz-Buzz 関数 (疑似コード) は、任意の正の整数nを取ります。if-else ステートメントに必要なコストと時間の代数的内訳に特に興味があります。最悪の場合の実行時間は O(n) です。

Fizz-Bizz(n)
  for i = 1 to n
    if (n % 3 == 0)
      print "fizz"
    if (n % 5 == 0)
      print "buzz"
    if (n % 3 != 0 and n % 5 != 0)
      print n

別のアルゴリズムの内訳の例:ここに画像の説明を入力

4

1 に答える 1

2

時間の複雑さはO(n)、ifステートメントがそれに実際に影響を与えないためです。ステートメントの複雑さは、if十分な大きさのデータセットにわたって一定です。

ステートメントは、if実際には 3 の倍数または 5 の倍数の反復で異なる量の作業を行う可能性がありますが、ループ反復ごとの余分な作業の量は に依存しませんn。n実際、大きくなるにつれて一定に平均化されます。

余談ですが、コードが間違っている可能性があると思います。15 の倍数では、 と の両方が出力fizz され buzzます。

編集のレベル (追加されたブレークダウン) で実行したい場合は、各ステートメントに任意のコストを割り当てるだけで済みます (このコストは、そのステートメントの 1 回の実行に対して一定です)。ステートメントが実行されます。ci

たとえば、最初のifシーケンスnの実行時間は、print "fizz"それらの 3 分の 1 で実行されn/3ます。したがって、次の表のようになります。

                           cost   times
Fizz-Buzz(n)
  for i = 1 to n           c1     n
    if (n % 3 == 0)        c2     n
      print "fizz"         c3     n / 3       [call this a]
    else
      if (n % 5 == 0)      c4     n - a
        print "buzz"       c5     (n - a) / 5 [call this b]
      else
        print n            c6     n - a - b

あなたの例に従ってそれらをすべて合計し（ と の式を代入しますn）a、最終b的には に依存するもの、つまりアルゴリズムになります。次のようになります。nO(n)

  c1*n + c2*n + c3*n/3   + c4*(n-a)   + c5*(n-a)/5     + c6*(n-a-b)
= c1*n + c2*n + (c3/3)*n + c4*(n-n/3) + (c5/5)*(n-n/3) + c6*(n-n/3-(n-n/3)/5)
= c1*n + c2*n + (c3/3)*n + c4*(2/3)*n + (c5/5)*(2/3)*n + c6*(n-n/3-(n-n/3)/5)
= c1*n + c2*n + (c3/3)*n + (c4*2/3)*n + (c5*2/15)*n    + c6*(n*8/15)
= c1*n + c2*n + (c3/3)*n + (c4*2/3)*n + (c5*2/15)*n    + (c6*8/15)*n

   /             1         2             2                8    \
= ( c1  + c2   + - c3    + - c4       + -- c5          + -- c6  ) * n
   \             3         3            15               15    /

括弧内のこれらの値はすべて実際には定数であり (定数の倍数であるため)、全体は の定数乗数ですn。

さて、上記の方程式に小さな間違いを見つけたとしても、私はそれほど驚かないでしょう。私はこのレベルの数学をかなりの年にわたって行っていません。宿題とあなたはそれを逐語的にコピーしてみてください:-)

しかし、あなたが見つけそうな唯一の間違いは、定数乗数自体の値です。それはまだいくつかの説明の一定の乗数になるでしょう、私はそれを保証します.

于 2014-06-26T06:21:54.873 に答える