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

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

1. AO(log n)
2. BO(1)
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 Theta)
2. Bo (little o)
3. CO (Big O)
4. DΩ (Big Omega)

Thời gian chạy trong trường hợp trung bình mô tả điều gì?

1. AThời gian kỳ vọng trên một phân phối cho trước của các đầu vào kích thước n
2. BThời gian trên loại máy tính phổ biến nhất
3. CGiá trị ở giữa thời gian chạy trường hợp tốt nhất và trường hợp xấu nhất
4. DThời gian cho một đầu vào có độ dài trung bình

Quicksort luôn dùng phần tử đầu tiên làm pivot. Trên đầu vào nào nó thể hiện hành vi xấu nhất?

1. AMột mảng mà các phần tử đều khác nhau
2. BMột mảng đã được sắp xếp
3. CMột mảng có thứ tự ngẫu nhiên
4. DMột mảng có độ dài 2

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

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

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. BKhông, vì n³ nhỏ hơn n² khi n lớn
3. CĐúng, nhưng chỉ khi n nhỏ hơn 100
4. DĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³

Phải chứng minh hai điều nào để chứng tỏ một bài toán quyết định X là NP-đầy đủ?

1. AX thuộc P, và X quy dẫn về SAT
2. BX thuộc NP, và một bài toán NP-đầy đủ đã biết quy dẫn về X trong thời gian đa thức
3. CX không có thuật toán đa thức, và X quyết định được
4. DX quy dẫn về một bài toán trong P, và X thuộc NP

Phép nhân Karatsuba thỏa mãn T(n) = 3T(n/2) + O(n). Nghiệm của nó là gì?

1. AΘ(n^{log₂ 3}), khoảng n^1,585
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(n³)