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ó chỉ có thể chạy một lần
2. BThời gian chạy của nó không tăng theo kích thước đầu vào
3. CNó luôn mất đúng một giây
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 3 giây khi n = 1 triệu. Khoảng bao lâu khi n = 2 triệu?

1. A12 giây
2. B3 giây
3. C6 giây
4. D9 giây

Ký hiệu nào mô tả cận dưới của tốc độ tăng?

1. Ao (little o)
2. BO (Big O)
3. CΩ (Big Omega)
4. DΘ (Big Theta)

Bạn sắp xếp một mảng n phần tử một lần rồi trả lời k truy vấn thuộc về bằng tìm kiếm nhị phân. Tổng chi phí là bao nhiêu?

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

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

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

Độ phức tạp thời gian của Fibonacci đệ quy ngây thơ (fib(n) = fib(n−1) + fib(n−2)) là:

1. AHằng số
2. BHàm mũ
3. CTuyến tính
4. DLogarit

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. ALuôn chọn phần tử đầu tiên
2. BChọn pivot đồng đều ngẫu nhiên
3. CSắp xếp đầu vào trước khi chạy quicksort
4. DChỉ dùng đệ quy ở phía bên trái

Chi phí thời gian và không gian của việc tính số Fibonacci thứ n bằng một vòng lặp chỉ giữ hai giá trị cuối là bao nhiêu?

1. AThời gian O(n) và không gian O(n)
2. BThời gian O(2ⁿ) và không gian O(1)
3. CThời gian O(log n) và không gian O(n)
4. DThời gian O(n) và không gian O(1)