計算複雜度

電腦科學的核心概念

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

複雜度類別

複雜度類別

• 多項式時間（P）
• 非確定性多項式時間（NP）
• NP-Complete（NP 完全）
• NP-Hard（NP 困難）

P（多項式時間）

Complexity Class -->	P (Polynomial Time)
What it means	可快速且有效率地求解
Example	排序清單
Analogy	「依字母順序歸檔文件」
Key Point	在計算上屬於「容易」的問題

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

NP（非確定性多項式時間）

Complexity Class -->	NP (Non-deterministic Polynomial Time)
What it means	解答可快速驗證，但找新解很難
Example	驗證數獨是否正確
Analogy	「在資訊缺漏下尋找特定文件」
Key Point	驗證解答「容易」，找新解困難

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

NP-Complete（NP 完全）

Complexity Class -->	NP-Complete
What it means	NP 中最難者；特別在於能代表解出所有 NP
Example	旅行推銷員問題
Analogy	「解超難拼圖：易驗證、難求解」
Key Point	尚無已知有效率解法；一旦找到，將解出所有 NP

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

NP-Hard（NP 困難）

Complexity Class -->	NP-Hard
What it means	與 NP-Complete 一樣難或更難
Example	具複雜相依且不可驗證的最佳化排程
Analogy	「多限制下找最佳會議時間，且無法快速驗證」
Key Point	實務上可能無法可行地解出

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

P=NP 的大哉問？

一起來練習吧！

電腦科學的核心概念