DAA-スペースの複雑さ
この章では、アルゴリズムが必要とするスペースの量に関する計算問題の複雑さについて説明します。
空間の複雑さは、時間の複雑さの多くの機能を共有し、計算の難しさに応じて問題を分類するためのさらなる方法として機能します。
スペースコンプレキシティとは何ですか？
スペースの複雑さは、アルゴリズムへの入力量の観点から、アルゴリズムが使用するメモリ（スペース）の量を表す関数です。
私たちはよく話します extra memory入力自体を格納するために必要なメモリはカウントしません。ここでも、これを測定するために自然な（ただし固定長の）単位を使用します。
バイトを使用することもできますが、使用する整数の数、固定サイズの構造体の数などを使用する方が簡単です。
結局、私たちが思いついた関数は、単位を表すために必要な実際のバイト数とは無関係になります。
使用されるスペースが最小限または明白であるため、スペースの複雑さが無視されることがありますが、時間の複雑さと同じくらい重要な問題になる場合があります。
定義
しましょう 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 is a language decided by an O(f(n)) space deterministic TM}
SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}
PSPACE は、決定論的チューリングマシンの多項式空間で決定可能な言語のクラスです。
言い換えると、 PSPACE = Uk SPACE (nk)
サヴィッチの定理
空間の複雑さに関連する最も初期の定理の1つは、サヴィッチの定理です。この定理によれば、決定論的マシンは、少量のスペースを使用して非決定性マシンをシミュレートできます。
時間の複雑さのために、そのようなシミュレーションは時間の指数関数的な増加を必要とするようです。スペースの複雑さについて、この定理は、を使用する非決定性チューリングマシンがf(n) スペースは、を使用する決定論的TMに変換できます f2(n) スペース。
したがって、サヴィッチの定理は、任意の関数について、$ f \ Colon N \ rightarrow R ^ + $と述べています。ここで、$ f（n）\ geqslant n $
NSPACE(f(n)) ⊆ SPACE(f(n))
複雑さクラス間の関係
次の図は、さまざまな複雑度クラス間の関係を示しています。
これまで、このチュートリアルではPクラスとNPクラスについては説明していません。これらについては後で説明します。