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(n²)
3. CO(5n)
4. DO(3n²)

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

1. AΩ (Big Omega)
2. BΘ (Big Theta)
3. CO (Big O)
4. Do (little o)

Sắp xếp chọn hoạt động như thế nào?

1. ANó chia mảng làm đôi rồi trộn lại
2. BNó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu
3. CNó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyển
4. DNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

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

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

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

2²ⁿ có thuộc O(2ⁿ) không?

1. AKhông, vì 2²ⁿ tăng chậm hơn 2ⁿ
2. BCó, vì cả hai đều là hàm mũ
3. CCó, vì các hệ số hằng trong số mũ luôn bị bỏ qua trong Big O
4. DKhông, vì 2²ⁿ = 4ⁿ và 4ⁿ / 2ⁿ = 2ⁿ tăng không giới hạn

Sự khác biệt giữa một bài toán bất khả quyết định và một bài toán không khả thi (intractable) là gì?

1. ABài toán bất khả quyết định thuộc NP, còn bài toán không khả thi thuộc P
2. BCả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán
3. CBài toán bất khả quyết định không có thuật toán nào cho mọi đầu vào; bài toán không khả thi có thuật toán, nhưng quá chậm
4. DBài toán không khả thi không thể giải bằng bất kỳ thuật toán nào, còn bài toán bất khả quyết định chỉ cần thời gian hàm mũ