Design-and-analysis-of-algorithms-space-complexities
DAA-スペースの複雑さ
この章では、アルゴリズムが必要とするスペースの量に関する計算問題の複雑さについて説明します。
スペースの複雑さは、時間の複雑さの多くの特徴を共有し、計算の難しさに従って問題を分類するさらなる方法として機能します。
スペースの複雑さとは何ですか？
スペースの複雑さは、アルゴリズムへの入力の量に関して、アルゴリズムが使用するメモリ（スペース）の量を記述する関数です。
入力自体を保存するのに必要なメモリをカウントするのではなく、必要な*余分なメモリ*について話します。 繰り返しますが、これを測定するために自然な（ただし固定長の）ユニットを使用します。
バイトを使用することもできますが、使用する整数の数、固定サイズの構造体の数などを使用する方が簡単です。
最終的に、私たちが思いつく関数は、ユニットを表現するのに必要な実際のバイト数とは無関係になります。
スペースの複雑さは、使用されるスペースが最小限および/または明らかであるため無視される場合がありますが、時間の複雑さと同じくらい重要な問題になる場合があります
定義
*M* をすべての入力で停止する決定論的な* Turing machine（TM）*とします。 *M* のスペースの複雑さは関数$ f \ colon N \ rightarrow N $です。ここで、 *_ f（n）_* はテープのセルの最大数で、 *M* は長さ *M* の入力をスキャンします。 *M* のスペースの複雑さが *_f（n）_* である場合、 *M* はスペース *_f（n）_* で実行されると言えます。漸近表記を使用して、チューリングマシンの空間の複雑さを推定します。
$ f \ colon N \ rightarrow R ^ + $を関数とします。 スペースの複雑さのクラスは次のように定義することができます-
*_SPACE = \ {L | LはO（f（n））空間決定論的TM} _* によって決定される言語です*_SPACE = \ {L | Lは、O（f（n））空間によって決定される言語です。非決定的TM} _**PSPACE* は、決定論的チューリングマシン上の多項式空間で決定可能な言語のクラスです。つまり、 _ PSPACE = U〜k〜SPACE（n ^ k ^）_
サビッチの定理
スペースの複雑さに関連する最も初期の定理の1つは、サビッチの定理です。 この定理によれば、決定論的マシンは、少量のスペースを使用して非決定論的マシンをシミュレートできます。
時間の複雑さのために、そのようなシミュレーションは時間の指数関数的な増加を必要とするようです。 スペースの複雑さについて、この定理は、 _ f（n）' スペースを使用する非決定論的チューリングマシンは、 ' f ^ 2 ^（n）_ スペースを使用する決定論的TMに変換できることを示しています。
したがって、サヴィッチの定理は、任意の関数について、$ f \ colon N \ rightarrow R ^ + $であると述べています。ここで、$ f（n）\ geqslant n $
*_NSPACE（f（n））⊆SPACE（f（n））_*複雑性クラス間の関係
次の図は、さまざまな複雑度クラス間の関係を示しています。
これまで、このチュートリアルではPクラスとNPクラスについては説明していません。 これらについては後で説明します。
