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

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

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

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

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

Thuật toán sắp xếp nào chọn một pivot và phân hoạch mảng thành các phần tử nhỏ hơn và lớn hơn?

1. ASắp xếp trộn
2. BQuicksort
3. CSắp xếp chèn
4. DSắp xếp nổi bọt

Cận dưới của sắp xếp dựa trên so sánh trong trường hợp xấu nhất là:

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

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

Quy hoạch động hữu ích khi một bài toán có:

1. AMột vòng lặp duy nhất
2. BChỉ các đầu vào ngẫu nhiên
3. CHoàn toàn không có bài toán con, nên có thể giải trong một bước
4. DCác bài toán con chồng lặp và cấu trúc con tối ưu

Phép nhân Karatsuba thỏa mãn T(n) = 3T(n/2) + O(n). Nghiệm của nó là gì?

1. AΘ(n^{log₂ 3}), khoảng n^1,585
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n log n)

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. AKhô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
2. BCó, nên cận dưới là sai
3. CCó, nhưng chỉ với mảng ngắn hơn 100
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