|
|||||
|
|
| 时间复杂性和空间复杂性研究 | |
| 引用本文： | 高强,徐心和.时间复杂性和空间复杂性研究[J].智能系统学报,2014(5). |
| 作者姓名： | 高强 徐心和 |
| 作者单位： | 东北大学信息科学与工程学院,辽宁沈阳,110004 |
| 基金项目： | 国家自然科学基金资助项目(61370153)． |
| 摘 要： | 计算复杂性是衡量问题求解的难易程度的。研究问题的计算复杂性，可以明确该问题是否存在有效的求解算法。介绍并分析了计算理论的一些基本概念，论述了时间复杂性（包括P、NP、NP-hard、NP-complete和EXPTIME）和空间复杂性（包括PSPACE、NPSPACE、PSPACE-hard和PSAPCE-complete）中的各个主要分类。最后分析了各个复杂性类之间的关系。 |
| 关 键 词： | 计算复杂性 图灵机 确定型多项式时间复杂性 非确定型多项式时间复杂性 非确定型多项式时间复杂性的完全问题 确定型多项式空间复杂性 确定型多项式空间复杂性的完全问题 可归约性 |
Reseacr h on time complexity and space complexity |
|
| GAO Qiang,XU Xinhe.Reseacr h on time complexity and space complexity[J].CAAL Transactions on Intelligent Systems,2014(5). | |
| Authors: | GAO Qiang XU Xinhe |
| Abstract: | |
| Keywords: | computational complexity Turing machine P NP NP-complete PSAPCE PSAPCE-complete re-ducibility |
| 本文献已被 万方数据 等数据库收录！ | |