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. BO (Big O)
3. CΘ (Big Theta)
4. Do (little o)

Độ phức tạp thời gian của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

1. AO(E log V)
2. BO(V²)
3. CO(V × E)
4. DO(V + E)

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

1. AO(1)
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. AĐúng, nhưng chỉ khi n nhỏ hơn 100
2. BKhông, vì Big O phải luôn cho tốc độ tăng chính xác của hàm
3. CĐúng, vì Big O là cận trên và n² tăng không nhanh hơn n³
4. DKhông, vì n³ nhỏ hơn n² khi n lớn

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

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

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

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

Thuật toán Strassen nhân ma trận bằng 7 thay vì 8 phép nhân đệ quy các khối nửa kích thước. Thời gian chạy của nó là bao nhiêu?

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

Định nghĩa nào của lớp NP là đúng?

1. ACác bài toán quyết định có câu trả lời "có" kiểm chứng được trong thời gian đa thức khi cho một chứng chỉ
2. BCác bài toán không phải đa thức
3. CCác bài toán mà không thuật toán nào giải được
4. DCác bài toán không thể giải trong thời gian đa thức