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

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

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

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig Theta
2. BBig Omega
3. CLittle omega
4. DBig O

Một bài toán thường được gọi là khả thi (tractable) nếu:

1. ANó có thể được giải trong thời gian hằng số
2. BNó có thể được giải trong thời gian đa thức
3. CNó không có lời giải
4. DNó chỉ có thể được giải bằng cách thử mọi khả năng

Có đúng không khi nói một thuật toán O(n²) cũng là O(n³)?

1. AKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
2. BĐúng, nhưng chỉ khi n nhỏ hơn 100
3. CKhông, vì n³ nhỏ hơn n² khi n lớn
4. DĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³

Công thức truy hồi T(n) = 2T(n/2) + O(n) có nghiệm là:

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

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. ASắp xếp đầu vào trước khi chạy quicksort
2. BLuôn chọn phần tử đầu tiên
3. CChỉ dùng đệ quy ở phía bên trái
4. DChọn pivot đồng đều ngẫu nhiên

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

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