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 3 giây khi n = 1 triệu. Khoảng bao lâu khi n = 2 triệu?

1. A9 giây
2. B12 giây
3. C6 giây
4. D3 giây

Một phép toán chạy trong thời gian O(1) có nghĩa là gì?

1. ANó luôn mất đúng một giây
2. BThời gian chạy của nó không tăng theo kích thước đầu vào
3. CNó chỉ có thể chạy một lần
4. DNó xử lý đúng một phần tử mỗi giây thời gian chạy

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. A8 giây
2. B2 giây
3. C4 giây
4. D1 giây

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

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

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. ASắp xếp trộn đã là O(n)
2. BSắp xếp trộn không có cấu trúc đệ quy
3. CQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng
4. DCác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng

Độ 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(mn log n)
2. BO(mn)
3. CO(m + n)
4. DO(2^m+n)

Phát biểu nào về việc chọn phần tử nhỏ thứ k của một mảng chưa sắp xếp là đúng?

1. AViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp
2. BViệc chọn chỉ có thể thực hiện trong O(n²)
3. CQuickselect chạy trong thời gian kỳ vọng O(n), và trung vị của các trung vị đảm bảo O(n) trong trường hợp xấu nhất
4. DQuickselect chạy trong O(log n) ở trường hợp xấu nhất, vì nó chỉ đệ quy một phía của phần tử chốt

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