5

チューリングマシンの時間計算量と空間計算量の定義は同じであり、それらを区別することはできないと思います。

私を助けてください。ありがとう。

4

2 に答える 2

12

チューリングマシンに関しては、時間計算量は、マシンが何らかの入力で起動されたときにテープが移動する回数の尺度です。スペースの複雑さは、マシンの実行時に書き込まれるテープのセル数を指します。

TMの時間計算量は、その空間計算量に関連しています。特に、TMのチュースペースの複雑さが入力wに対してf（w）である場合、テープは少なくともf（w）ステップ移動してその数を書き出す必要があるため、その時間計算量は少なくともf（w）でなければなりません。セル。さらに、TMにテープアルファベットΓと状態のセットQがある場合、入力w上のTMの空間計算量がf（w）であり、TMがwで停止する場合、時間計算量は最大で|Q|Γでなければなりません。f（n）。これを確認するには、実行の任意の時点でのTMの構成がf（n）テープセルの文字列で構成され、各セルに任意のテープシンボルを含めることができ、|Q|のいずれかに含めることができることに注意してください。州。

この区別の興味深い例は、線形拘束オートマトン（LBA）のような制限付きチューリングマシンを見ると表示されます。これは、入力のサイズに比例したスペースにテープが制限されているチューリングマシンです。TMの空間計算量はO（n）に制限されていますが、特定のLBAの時間計算量は、入力のサイズで指数関数的になる可能性があります。

お役に立てれば！

于 2011-08-21T08:57:13.787 に答える
5

時間計算量は、アルゴリズムが回答を生成するのにかかる時間の尺度です。

スペースの複雑さは、アルゴリズムがプロセスで使用するメモリの量の尺度です。

例として、整数1..nの合計を計算する問題を考えてみましょう。単純なアルゴリズムは次のように機能します。

procedure sum(n)
  total := 0
  for i = 1 to n
    total := total + a[n]
  return total

このアルゴリズムの時間計算量はO（n ）です。これは、ループが明らかにn回の反復を通過するためです。一方、必要なメモリはtotalとiのみであり、 nに依存しないため、スペースの複雑さはO（1）です。

于 2011-08-21T08:20:55.847 に答える