5

以下のアルゴリズムの漸近的な空間と時間の複雑さを、(定数の 12 桁とは異なる) 任意の長さの初期入力数に対して適切な条件で提供するように求められます。

1 for i = 2 to 12
2     if d[i] == d[i-1]
3        d[i] = (d[i] + 3) mod 10

このアルゴリズムは 12 桁の数値に適用され、各桁は配列に格納されますd[](したがってd[1]、 、d[2]、...がありますd[12]) 。

時間の複雑さはわかりましたO(n)が、空間の複雑さをどのように判断すればよいですか?

4

1 に答える 1

6

通常、スペースの複雑さを測定するには、コードの実行に必要なすべての情報を保持するために必要な余分なスペースを調べる必要があります。課題は、コード実行の存続期間全体にわたって多くの場合、スペースを再利用できることです。

この場合、コードを保存するための余分なスペースが必要です

  • ループ内の一時的な計算の値、
  • i の値、および
  • プログラムカウンターなどの各種データ

これらのうち最後の 2 つは O(1) スペースを占有します。スタック ポインターなどの補助データ用に i と定数スペースが 1 つしかないためです。ループの各反復には、一時変数用に O(1) スペースが必要ですが、このスペースは再利用できることに注意してください。これは、各ループ反復が終了した後、これらの一時変数用のスペースが不要になり、次の処理で再利用できるためです。反復。したがって、必要な合計スペースはちょうど O(1) です。

(注...時間計算量が O(n) であると確信していますか?配列の大きさに関係なく、反復回数は一定であることに注意してください。)

お役に立てれば！

于 2013-09-15T22:57:26.680 に答える