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

Big O của 3n² + 5n + 2 là gì?

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

Thời gian chạy nào sau đây là đa thức?

1. AO(n³)
2. BO(n!)
3. CO(2ⁿ)
4. DO(nⁿ)

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. A1 giây
2. B4 giây
3. C8 giây
4. D2 giây

Công thức truy hồi T(n) = 2T(n/2) + O(n) có nghiệm là:

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

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

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

Thuật toán Floyd–Warshall tính gì, và nhanh đến mức nào?

1. AĐường đi ngắn nhất giữa mọi cặp đỉnh trong O(V³)
2. BMột thứ tự tô-pô trong O(V²)
3. CMột cây khung nhỏ nhất trong O(E log V)
4. DĐường đi ngắn nhất từ một đỉnh nguồn đến mọi đỉnh khác trong O(V + E)

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, vì sắp xếp chèn không phải là sắp xếp dựa trên so sánh
2. BCó, nên cận dưới là sai
3. CKhô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
4. DCó, nhưng chỉ với mảng ngắn hơn 100

Độ phức tạp thời gian của việc xây dựng một đống nhị phân từ n phần tử chưa sắp xếp bằng phương pháp từ dưới lên là gì?

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