补充资料：空间复杂性

空间复杂性
space complexity

kong!一an fuzaxing空间复杂性(sPace co.LPlexity)解答问题时算法所需要的空间。算法的空间需求是指计算所需要的计算机存储量。在图灵机计算模型中，使用的空间量定义为读写头访问的不同的带方格数。因为访问的带方格数不可能多于计算步骤，所以任何在T(n)时间内可解的问题也必可在T(n)空间内可解。更精确地说，输人本身占有的空间是不应该计算在空间用量内的，所以图灵机的带分成输人带和工作带，空间复杂性是指图灵机运行时带头读写工作带上经过的带方格数。如果是随机存储器模型，空间复杂性是指工作单元数(有时按工作单元的二进位数)。大量实例表明，空间复杂性与时间复杂性一样，也是一个与计算模型无关的概念。 在多项式时间内可解的所有问题都可以在多项式空间内解决，但是否存在在多项式空间内可解的问题不能在多项式时间内解决，这仍然是一个未解决的问题。一般认为有这样的问题存在。此即著名的P护PSP户L(二E问题。 用图灵机计算模型，可以得到很简单的带压缩定理:如果语言L能够被图灵机M在空间:(n)内接受，。是任意(0，l)之间的实数，则L可以被另一图灵机M‘在空间cs(n)内接受。 这表明在空间复杂性函数中，常系数是一个次要的因素。人们更为关心的是空间复杂性在输人规模趋于co时的渐近性态，即它的增长率。 还有一个与时间复杂性截然不同的定理是:如果语言L能够被不确定图灵机M在空间:(n)内接受，则L可以被另一确定图灵机M’在空间:2(n)内接受。 并行算法的空间复杂性和时间复杂性有相互折算的关系，空间耗费大，即并行程度高，则并行算法的执行时间可以降低，但也不是说空间用量任意地增加，并行时间复杂性可以任意地小，故权衡并行算法的时空折衷关系，设计好的空间体系结构(如n-维立方体，星形图等)是并行算法空间复杂性研究主要关心的问题。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。