是否可以从图灵空间复杂性中估算RAM？

Question

图灵机可以在两个空间（磁带上的内存空间）和时间中考虑复杂性。

有Pspace和Expspace之类的类。

此外，我们可以介绍肯定在Pspace中的算法。

http://www.springerlink.com/content/3HQTQ11MQJBQFJ2G/

但是，当我实际编码程序时，某些程序的运行速度比其他程序快，有些程序的内存（RAM）足迹比其他程序更小。

据推测，如果我编码PSPACE算法来解决问题X以及一个Expspace算法以解决相同的问题，那么Expspace程序应该使用的RAM比PSPACE代码更多。

是否有任何方法可以根据起始算法的理论评级来估计将涉及多少RAM？

Answer 1

原则上。实际上，有时。

首先，您必须了解什么复杂性分析实际上是什么意思（查看教科书中的定义）。 Pspace仅表示所需的空间受输入大小的多项式函数的界定。它不会告诉您什么是边界函数，或者使用的实际空间是什么。因此，您不能仅仅知道在Pspace中知道一种算法就可以解决有关RAM的任何事情。

如果您知道Pspace中的算法，则可以假设它使用的空间不仅仅是 有限 通过多项式，它是 描述 通过多项式。这可能不是真的，但是对于许多算法，这是真的。然后，您可以计算（或测量）用于各种不同输入尺寸的空间，并尝试将多项式与数据匹配。

通常，这是相当徒劳的（因为不知道多项式的顺序，因此有很多可能的拟合）。但是实际上，如果您知道所使用的空间是O（n），并且您有一些知道哪种输入会产生最差的空间使用，那么您可以做出相当准确的预测。如果需要10MB的RAM来处理1MB的输入，而20MB的RAM才能处理2MB的输入，则经常需要大约100MB的RAM来处理10MB的输入。但是，您只会从对算法更详细的知识中获得这种见解，而不仅仅是知道其具有多项式空间复杂性。

Answer 2

据推测，如果我编码PSPACE算法来解决问题X以及一个Expspace算法以解决相同的问题，那么Expspace程序应该使用的RAM比PSPACE代码更多。

你假设错了。

这些复杂性类描述了执行算法所需的记忆的渐近生长。他们绝对没有告诉您所需的RAM数量。

基本上，对于某些问题 n, ，高于该尺寸的expspace将比PSPACE使用更多的内存，但对于以下任何内容 n, ，你真的不能说什么（就像o（n）²）算法的运行速度可能比小的O（n）算法快 n).