图灵机可以同时考虑空间(磁带上的存储空间)和时间的复杂性。
有PSPACE、EXPSPACE等类。
此外，我们可以提出绝对属于 PSPACE 的算法。
http://www.springerlink.com/content/3hqtq11mqjbqfj2g/
但是，当我实际编写程序时，有些程序比其他程序运行得更快，有些程序的内存 (RAM) 占用空间比其他程序小。
大概如果我编写一个 PSPACE 算法来解决问题 X 并编写一个 EXPSPACE 算法来解决相同的问题，则 EXPSPACE 程序应该比 PSPACE 代码使用更多的 RAM。
是否有任何方法可以根据起始算法的理论评级来估计将涉及多少 RAM？
最佳答案
Presumably if I code a PSPACE algorithm to solve problem X and also an EXPSPACE algorithm to solve the same problem, the EXPSPACE program should use much more RAM than the PSPACE code.
你猜错了。
这些复杂度类别描述了执行算法所需内存的渐近增长。他们绝对不会告诉您所需的实际 RAM 量。
基本上，对于某些规模的问题 n，高于该规模的 EXPSPACE 将比 PSPACE 使用更多的内存，但对于低于 n 的任何问题，你真的不能说什么(就像 O(n2) 算法可能比小 n 的 O(n) 算法运行得更快。
关于performance - 是否可以根据图灵空间复杂度估算所需的 RAM？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4296386/