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

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A2 giây
2. B8 giây
3. C1 giây
4. D4 giây

Thời gian chạy nào sau đây là đa thức?

1. AO(n³)
2. BO(2ⁿ)
3. CO(nⁿ)
4. DO(n!)

Độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

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

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 20
2. BKhoảng 1,000
3. CKhoảng 100
4. DKhoảng 500,000

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

Độ phức tạp thời gian của thuật toán quy hoạch động chuẩn cho dãy con chung dài nhất của các chuỗi có độ dài m và n là gì?

1. AO(2^m+n)
2. BO(m + n)
3. CO(mn log n)
4. DO(mn)

Bài toán cái túi 0/1 giải bằng quy hoạch động mất thời gian O(nW). Vì sao điều này được gọi là giả đa thức?

1. AVì thuật toán là ngẫu nhiên và thời gian chạy thay đổi theo từng đầu vào
2. BVì nó chỉ hoạt động khi W = 0
3. CW là một giá trị số, nên thời gian là hàm mũ theo số bit dùng để viết W
4. DVì n luôn nhỏ

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 bất khả quyết định thuộc NP, còn bài toán không khả thi thuộc P
2. BCả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán
3. CBà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ũ
4. DBà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