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. A3 giây
2. B9 giây
3. C12 giây
4. D6 giây

Độ 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²)
2. BO(n log n)
3. CO(1)
4. DO(n)

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

Phân tích khấu hao đo lường điều gì?

1. AChi phí của một thuật toán trên đầu vào tốt nhất
2. BChi phí kỳ vọng trên các đầu vào ngẫu nhiên
3. CChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
4. DChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

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

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. ACác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
2. BMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu
3. CCơ số chỉ quan trọng với n nhỏ
4. DLogarit luôn được làm tròn thành số nguyên

Phát biểu nào về P và NP là đúng?

1. AMọi bài toán trong P cũng thuộc NP
2. BCác bài toán NP không thể được kiểm chứng nhanh
3. CNP có nghĩa là "không đa thức"
4. DĐã được chứng minh rằng P ≠ NP

Sắp xếp chèn chạy trong O(n) trên đầu vào đã sắp xếp. Điều này có mâu thuẫn với cận dưới Ω(n log n) cho sắp xếp dựa trên so sánh không?

1. ACó, nhưng chỉ với mảng ngắn hơn 100
2. BKhông, cận dưới áp dụng cho trường hợp xấu nhất trên mọi đầu vào, không phải cho từng đầu vào
3. CCó, nên cận dưới là sai
4. DKhông, vì sắp xếp chèn không phải là sắp xếp dựa trên so sánh