计算复杂性

计算机科学概念

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

复杂度类别

复杂度类别

• 多项式时间（P）
• 非确定性多项式时间（NP）
• NP-Complete（NP 完全）
• NP-Hard（NP 困难）

P（多项式时间）

复杂度类别 -->	P（多项式时间）
含义	可快速、高效地求解
示例	对列表排序
类比	"按字母顺序归档文件"
要点	计算上被视为"容易"

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

NP（非确定性多项式时间）

复杂度类别 -->	NP（非确定性多项式时间）
含义	解可验证，但寻找新解很难
示例	验证数独解是否正确
类比	"在信息不全时找特定文件"
要点	验证"容易"，找新解很难

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

NP-Complete（NP 完全）

复杂度类别 -->	NP-Complete
含义	NP 中最难者。特殊之处：可用来解决所有 NP 问题
示例	旅行商问题
类比	"复杂拼图：易验证，难求解"
要点	目前无已知高效解；一旦找到，将解决所有 NP

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

NP-Hard（NP 困难）

复杂度类别 -->	NP-Hard
含义	与 NP-Complete 一样难或更难
示例	具有复杂依赖且不可高效验证的最优调度
类比	"含诸多约束且无法快速验证的最优会议安排"
要点	实践中可能无法求解

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

P=NP 的重大谜题？

Passons à la pratique !

计算机科学概念