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

Hàm nào sau đây tăng chậm nhất khi n lớn dần?

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

Tìm kiếm nhị phân đòi hỏi gì ở đầu vào của nó?

1. AMảng phải được sắp xếp
2. BMảng không được có quá 1000 phần tử
3. CMảng chỉ được chứa số dương
4. DĐộ dài mảng phải là lũy thừa của hai

Thời gian chạy của sắp xếp đếm cho n số nguyên trong khoảng từ 0 đến k là bao nhiêu?

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

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

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

Vì sao cơ số của logarit thường bị bỏ trong Big O, như trong O(log n)?

1. ACơ số chỉ quan trọng với n nhỏ
2. BCác logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng
3. CLogarit luôn được làm tròn thành số nguyên
4. DMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu

Một hàm chạy một vòng lặp n lần lặp rồi, tách biệt, một vòng lặp khác n lần lặp. Độ phức tạp thời gian của nó là gì?

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

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

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

Thời gian chạy của thuật toán Dijkstra với đống nhị phân trên đồ thị có V đỉnh và E cạnh là bao nhiêu?

1. AO(V³)
2. BO((V + E) log V)
3. CO(V + E)
4. DO(V × E)