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. ABig O
2. BLittle omega
3. CBig Omega
4. DBig Theta

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

1. AO(n log n)
2. BO(1)
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. AĐộ dài mảng phải là lũy thừa của hai
2. BMảng chỉ được chứa số dương
3. CMảng phải được sắp xếp
4. DMảng không được có quá 1000 phần tử

Độ phức tạp thời gian của việc nhân hai ma trận n × n bằng ba vòng lặp lồng nhau chuẩn là gì?

1. AO(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)

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 log n)
3. CΩ(n)
4. DΩ(log n)

Cận nào là đúng cho log(n!)?

1. AΘ(n)
2. BΘ(log n)
3. CΘ(n²)
4. DΘ(n log 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. ACả hai đều có nghĩa là bài toán hoàn toàn không có thuật toán
2. BBà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
3. CBà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ũ
4. DBà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