图灵机可以考虑空间（磁带上的内存空间）和时间的复杂性。
有诸如 PSPACE 和 EXPSPACE 之类的类。
此外，我们可以提出肯定存在于 PSPACE 中的算法。
http://www.springerlink.com/content/3hqtq11mqjbqfj2g/
但是，当我实际编写程序时，有些程序比其他程序运行得更快，有些程序的内存 (RAM) 占用空间比其他程序小。
大概如果我编写一个 PSPACE 算法来解决问题 X 和一个 EXPSPACE 算法来解决同样的问题，那么 EXPSPACE 程序应该比 PSPACE 代码使用更多的 RAM。
有没有办法根据起始算法的理论评级来估计将涉及多少 RAM？
大概如果我编写一个 PSPACE 算法来解决问题 X 和一个 EXPSPACE 算法来解决同样的问题，那么 EXPSPACE 程序应该比 PSPACE 代码使用更多的 RAM。
你猜错了。
这些复杂度类描述了执行算法所需的内存的渐近增长。他们绝对不会告诉您所需的实际 RAM 数量。
基本上，对于某些大小的问题n，超过该大小的 EXPSPACE 将使用比 PSPACE 更多的内存，但对于低于n的任何内容，您都不能说什么（就像 O(n 2 ) 算法可能比 O(n) 运行得更快小n的算法）。
原则上没有。在实践中，有时。
首先，您必须了解复杂性分析的实际含义（查看教科书中的定义）。PSPACE 只是意味着所需的空间受输入大小的多项式函数的限制。它没有告诉你那个边界函数是什么，或者实际使用的空间是什么。因此，仅通过知道 PSPACE 中的算法就无法计算出有关 RAM 的任何信息。
如果您知道 PSPACE 中的算法，您可能会假设它使用的空间不只是由多项式界定，而是由多项式描述。这可能不是真的，但对于许多算法来说它是真的。然后，您可以计算（或测量）用于各种不同输入大小的空间，并尝试将多项式与数据匹配。
一般来说，这是徒劳的（因为在不知道多项式的阶数的情况下，有无数种可能的拟合）。但在实践中，如果你知道使用的空间是 O(n)，并且你知道什么样的输入会产生最坏情况下的空间使用，那么你可以做出相当准确的预测。如果处理 1MB 的输入需要 10MB 的 RAM，而处理 2MB 的输入需要 20MB 的 RAM，那么处理 10MB 的输入通常需要大约 100MB 的 RAM。但是你只能从更详细的算法知识中获得这种洞察力，而不仅仅是知道它具有多项式空间复杂度。