计算机科学空间复杂度类本页总览空间复杂度类阐述 TIME 设 f:N→R+f:\mathbb N\to\mathbb R^+f:N→R+，定义空间复杂度类 SPACE(f(n))\operatorname{SPACE}(f(n))SPACE(f(n)) 是所有能在 O(f(n))O(f(n))O(f(n)) 渐近时间内由某种确定性 Turing 机判别的语言的集合。 NTIME 设 f:N→R+f:\mathbb N\to\mathbb R^+f:N→R+，定义空间复杂度类 NSPACE(f(n))\operatorname{NSPACE}(f(n))NSPACE(f(n)) 是所有能在 O(f(n))O(f(n))O(f(n)) 渐近时间内由某种非确定性 Turing 机判别的语言的集合。 两者的关系 Savitch 定理指出将非确定性 Turing 机转换为确定性 Turing 机时只需要使用平方大小的空间。 实例 性质 相关内容 参考文献