评估计算复杂性 - 蝈蝈俊
原文中文,约3200字,阅读约需8分钟。发表于: 。计算机科学评估计算复杂性,是看它消耗的资源,具体来说就是时间和内存(空间)。 基于时间和空间复杂性,我们有:\(NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE\) (其中 \(⊆\) 表示子集关系)。 图来自:https://en.wikipedia.org/wi
计算机科学评估计算复杂性主要考虑时间和空间复杂性。NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE。NL是非确定性对数空间,P是多项式时间,NP是非确定性多项式时间,PSPACE是多项式空间,EXPTIME是指数时间,EXPSPACE是指数空间。P问题易于找到解决方案,NP问题易于验证但难以找到解决方案。NP问题在优化问题、密码学、计划和调度问题、生物信息学和化学、网络设计、游戏理论和经济学等领域有广泛应用。