Độ phức tạp tính toán

Các Khái Niệm trong Khoa Học Máy Tính

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Các lớp độ phức tạp

Các lớp độ phức tạp

Ảnh động minh họa toàn bộ không gian độ phức tạp bài toán

Hình minh họa không gian bài toán P

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

Hình minh họa không gian bài toán P và NP

Lớp độ phức tạp -->	NP (Thời gian đa thức không xác định)
Ý nghĩa	Có thể kiểm chứng nghiệm nhanh, nhưng tìm nghiệm mới khó
Ví dụ	Kiểm tra lời giải Sudoku đúng
Ví von	"Tìm tài liệu cụ thể khi thiếu thông tin"
Điểm chính	Kiểm chứng "dễ", tìm nghiệm mới khó

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

Hình minh họa không gian bài toán P, NP và NP-Complete

Lớp độ phức tạp -->	NP-Complete
Ý nghĩa	Khó nhất trong NP; đặc biệt vì giải được mọi bài toán NP
Ví dụ	Bài toán người bán hàng (TSP)
Ví von	"Ghép puzzle phức tạp: kiểm tra dễ, giải khó"
Điểm chính	Chưa có thuật toán hiệu quả; nếu có, sẽ giải được mọi bài toán NP

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

Hình minh họa không gian bài toán P, NP, NP-Complete và NP-Hard

Lớp độ phức tạp -->	NP-Hard
Ý nghĩa	Khó như NP-Complete hoặc khó hơn
Ví dụ	Lập lịch tối ưu với phụ thuộc phức tạp và không kiểm chứng được
Ví von	"Chọn lịch họp tối ưu với nhiều ràng buộc và không thể kiểm nhanh"
Điểm chính	Có thể bất khả thi về mặt thực tiễn

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

Sơ đồ nêu câu hỏi nghiên cứu lâu đời: P=NP?

Các Khái Niệm trong Khoa Học Máy Tính