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 tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

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

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

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ó chỉ có thể được giải bằng cách thử mọi khả năng
3. CNó không có lời giải
4. DNó có thể được giải trong thời gian đa thức

Độ phức tạp thời gian của thuật toán Bellman–Ford trên đồ thị có V đỉnh và E cạnh là gì?

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

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

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

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 4 đồng; tối ưu là 3
2. BTham lam dùng 3 đồng; tối ưu là 3
3. CTham lam dùng 2 đồng; tối ưu là 2
4. DTham lam dùng 3 đồng; tối ưu là 2

Sự khác biệt giữa một bài toán bất khả quyết định và một bài toán không khả thi (intractable) là gì?

1. ABài toán không khả thi không thể giải bằng bất kỳ thuật toán nào, còn bài toán bất khả quyết định chỉ cần thời gian hàm mũ
2. BBài toán bất khả quyết định không có thuật toán nào cho mọi đầu vào; bài toán không khả thi có thuật toán, nhưng quá chậm
3. CBài toán bất khả quyết định thuộc NP, còn bài toán không khả thi thuộc P
4. DCả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán

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

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