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

Đặt vấn đề

B Phần lớn các thuật toán đã trình bày có độ phức tạp hàm đa thức - Câu hỏi | 0 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 ? 1 Trả lời

B 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) g Không. Bởi vì có những bài toán chúng ta chỉ 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ũ

B 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(n), (n), 0(1), O(n Ign) - 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ũ)

u 0(2n), bện"), On!)

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