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

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ALittle omega
2. BBig O
3. CBig Theta
4. DBig Omega

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

Sắp xếp trộn chuẩn dựa trên mảng dùng thêm bao nhiêu bộ nhớ?

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

Trong một mảng đã sắp xếp, bạn tìm hai phần tử có tổng bằng giá trị đích bằng cách di chuyển một con trỏ từ mỗi đầu vào trong. Độ phức tạp thời gian là bao nhiêu?

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

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

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

Độ phức tạp thời gian của thuật toán Bellman–Ford trên đồ thị có V đỉnh và E cạnh là gì?

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

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 log n)
4. DΘ(n³)

Phát biểu nào về ký hiệu little-o là đúng?

1. A2n = o(n), vì 2n tăng chậm
2. Bn = o(n²), nhưng n không phải o(n)
3. Cn² = o(n)
4. Dn = o(n), vì mọi hàm đều là little-o của chính nó