Phiếu bài tập Thuật toán và độ phức tạp có đáp án

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

1. AO(1)
2. BO(n)
3. CO(log n)
4. DO(n log n)

Big O của 3n² + 5n + 2 là gì?

1. AO(3n²)
2. BO(5n)
3. CO(n³)
4. DO(n²)

Ký hiệu nào mô tả cận dưới của tốc độ tăng?

1. AΩ (Big Omega)
2. Bo (little o)
3. CO (Big O)
4. DΘ (Big Theta)

Với các đồng xu 1, 3 và 4 và số tiền 6, phương pháp tham lam "đồng lớn nhất trước" dùng bao nhiêu đồng, so với tối ưu?

1. ATham lam dùng 3 đồng; tối ưu là 3
2. BTham lam dùng 3 đồng; tối ưu là 2
3. CTham lam dùng 2 đồng; tối ưu là 2
4. DTham lam dùng 4 đồng; tối ưu là 3

Cận dưới của sắp xếp dựa trên so sánh trong trường hợp xấu nhất là:

1. AΩ(n)
2. BΩ(n²)
3. CΩ(n log n)
4. DΩ(log n)

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. ALogarit luôn được làm tròn thành số nguyên
2. BMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu
3. CCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
4. DCơ số chỉ quan trọng với n nhỏ

Định lý Cook–Levin đã thiết lập điều gì?

1. AMọi bài toán NP đều giải được trong thời gian hàm mũ
2. BP không bằng NP
3. CBài toán dừng là bất khả quyết định
4. DBài toán thỏa mãn Boole (SAT) là NP-đầy đủ

Để chứng minh một bài toán mới X là NP-khó, bạn phải làm gì?

1. AChứng minh X không có thuật toán đa thức cho đầu vào nhỏ
2. BQuy dẫn một bài toán NP-khó đã biết về X trong thời gian đa thức
3. CChứng minh X kiểm chứng được trong thời gian đa thức
4. DQuy dẫn X về một bài toán NP-khó đã biết trong thời gian đa thức