チューリング マシンは、スペース (テープ上のメモリ スペース) と時間の両方で複雑さを考慮することができます。
PSPACE や EXPSPACE などのクラスがあります。
さらに、間違いなく PSPACE にあるアルゴリズムを提示できます。
http://www.springerlink.com/content/3hqtq11mqjbqfj2g/
しかし、実際にプログラムをコーディングすると、他のプログラムよりも高速に実行されるプログラムもあれば、メモリ (RAM) フットプリントが他のプログラムよりも小さいプログラムもあります。
おそらく、問題 X を解決するために PSPACE アルゴリズムをコーディングし、同じ問題を解決するために EXPSPACE アルゴリズムもコーディングする場合、EXPSPACE プログラムは PSPACE コードよりもはるかに多くの RAM を使用する必要があります。
開始アルゴリズムの理論上の評価に基づいて、RAM の使用量を見積もる方法はありますか?
おそらく、問題 X を解決するために PSPACE アルゴリズムをコーディングし、同じ問題を解決するために EXPSPACE アルゴリズムもコーディングする場合、EXPSPACE プログラムは PSPACE コードよりもはるかに多くの RAM を使用する必要があります。
あなたは間違っていると思います。
これらの複雑さのクラスは、アルゴリズムを実行するために必要なメモリの漸近的な増加を表します。実際に必要な RAM の量については何も教えてくれません。
基本的に、問題nのあるサイズでは、そのサイズを超える EXPSPACE は PSPACE よりも多くのメモリを使用しますが、n未満のものについては、実際には何も言えません (O(n 2 ) アルゴリズムが O(n) よりも高速に実行されるように)小さなnのアルゴリズム)。
原則としてNo. 実際には、時々。
最初に、複雑性分析が実際に何を意味するのかを理解する必要があります (教科書の定義を確認してください)。PSPACE は、必要なスペースが入力サイズの多項式関数によって制限されることを意味します。その境界関数が何であるか、または実際に使用されているスペースが何であるかはわかりません。したがって、アルゴリズムが PSPACE にあることを知っているだけでは、RAM について何も解決できません。
アルゴリズムが PSPACE にあることがわかっている場合、そのアルゴリズムが使用する空間は多項式によって制限されているだけでなく、多項式によって記述されていると仮定できます。それは真実ではないかもしれませんが、多くのアルゴリズムでは真実です。次に、さまざまな異なる入力サイズに使用されるスペースを計算 (または測定) し、多項式をデータに一致させようとすることができます。
一般に、これはかなり無駄です (多項式の次数を知らなければ、無限に多くの可能な近似があるため)。しかし、実際には、使用されるスペースがたとえば O(n) であることがわかっていて、どのような入力が最悪の場合のスペース使用を生み出すかをある程度知っていれば、かなり正確な予測を行うことができます。1MB の入力を処理するのに 10MB の RAM が必要で、2MB の入力を処理するのに 20MB の RAM が必要な場合、10MB の入力を処理するのに約 100MB の RAM が必要になることがよくあります。しかし、この洞察は、アルゴリズムが多項式空間の複雑さを持っていることを知っているだけではなく、アルゴリズムのより詳細な知識からのみ得られます。