Bài giảng Thuật toán nâng cao - Chương 10: Lớp các bài toàn NP đầy đủ - Nguyễn Thanh Bình

Đặt vấn đề

| | Phần lớn các thuật toán đã trình bày có độ phức tạp hàm đa thức

1 Câu hỏi

[ Tất cả các bài toán đều được giải quyết bởi thuật toán với thời gian thực thi

hàm đa thức ? Trả lời D Không. Có những bài toán không thể giải quyết được (tính dừng không xác

định) D Không. Bởi vì có những bài toán chúng ta chi biết các thuật toán giải quyết

chúng với thời gian thực thi hàm mũ

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

1 Lớp các vấn đề có thể giải quyết bởi thuật toán có độ phức tạp hàm đa thức

o O(n), O(n3), 0(1), O(n lg n) Lớp các vấn đề phức tạp hơn (giải quyết bởi thuật toán có độ phức tạp hàm mũ)

o(2"), O(n"), C(n!)

| | Cần phương tiện xác định một bài toán thuộc lớp nào ?