Phiếu bài tập Thuật toán và độ phức tạp có đáp á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. BNó chỉ có thể chạy một lần
3. CThời gian chạy của nó không tăng theo kích thước đầu vào
4. DNó xử lý đúng một phần tử mỗi giây thời gian chạy

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig O
2. BLittle omega
3. CBig Omega
4. DBig Theta

Một bài toán thường được gọi là khả thi (tractable) nếu:

1. ANó chỉ có thể được giải bằng cách thử mọi khả năng
2. BNó không có lời giải
3. CNó có thể được giải trong thời gian đa thức
4. DNó có thể được giải trong thời gian hằng số

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

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

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

Thời gian chạy của sắp xếp cơ số LSD trên n số nguyên có d chữ số trong cơ số k là bao nhiêu?

1. AO(dn log k)
2. BO(n log n)
3. CO(d(n + k))
4. DO(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 chỉ có thể thực hiện trong O(n²)
2. BQuickselect 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
3. CQuickselect 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
4. DViệc chọn luôn cần Ω(n log n) vì nó đòi hỏi sắp xếp

Dùng định lý chủ, T(n) = 8T(n/2) + O(n²) có nghiệm là:

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