电脑知识与技术
電腦知識與技術
전뇌지식여기술
Computer Knowledge and Technology
2015年
24期
40-42
,共3页
计算复杂性%复杂性类%时间复杂性%空间复杂性
計算複雜性%複雜性類%時間複雜性%空間複雜性
계산복잡성%복잡성류%시간복잡성%공간복잡성
computational complexity%complexity class%time complexity%space complexity
一个问题的计算复杂性(complexity)是指用计算机解决它的复杂程度,其度量标准:一是计算所需的步数或指令条数(即时间复杂度),二是计算所需的存储单元数(即空间复杂度).复杂度相似的所有问题构成的集合就是一个复杂性类(complexity class).该文探讨了在计算复杂性理论中常见的几种比较重要的计算复杂性类,研究了对计算复杂性归类的重要意义,以及复杂性类之间的一些关联.
一箇問題的計算複雜性(complexity)是指用計算機解決它的複雜程度,其度量標準:一是計算所需的步數或指令條數(即時間複雜度),二是計算所需的存儲單元數(即空間複雜度).複雜度相似的所有問題構成的集閤就是一箇複雜性類(complexity class).該文探討瞭在計算複雜性理論中常見的幾種比較重要的計算複雜性類,研究瞭對計算複雜性歸類的重要意義,以及複雜性類之間的一些關聯.
일개문제적계산복잡성(complexity)시지용계산궤해결타적복잡정도,기도량표준:일시계산소수적보수혹지령조수(즉시간복잡도),이시계산소수적존저단원수(즉공간복잡도).복잡도상사적소유문제구성적집합취시일개복잡성류(complexity class).해문탐토료재계산복잡성이론중상견적궤충비교중요적계산복잡성류,연구료대계산복잡성귀류적중요의의,이급복잡성류지간적일사관련.
The computational complexity of a problem is the complexity of solving it with a computer.One of its measures is to cal-culate the required number of steps or instructions (that is, the time complexity),the other is to calculate the number of storage unit (i.e., space complexity).The set of all the problems with similar complexity is a complexity class.In this paper,we discussed several common and important computational complexity classes in computational complexity theory,and studied the significance of the classification of computational complexity and some relations between the complexity classes.
