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 dưới của tốc độ tăng?

1. AΩ (Big Omega)
2. BO (Big O)
3. Co (little o)
4. DΘ (Big Theta)

f(n) = Θ(g(n)) có nghĩa là gì?

1. Af tăng nhanh hơn g một cách nghiêm ngặt
2. Bf tăng chậm hơn g một cách nghiêm ngặt
3. Cf tăng với cùng tốc độ như g, bị chặn trên và chặn dưới bởi các bội hằng của g
4. Df luôn nhỏ hơn g với mọi n, nên g chặn trên f nhưng không bao giờ chặn dưới

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

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

Một thuật toán tham lam:

1. ALuôn cho lời giải tối ưu
2. BThử mọi lời giải có thể
3. CChỉ dùng đệ quy
4. DĐưa ra lựa chọn tốt nhất cục bộ ở mỗi bước

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

Độ 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)
4. DO(n² log n)

Định nghĩa nào của lớp NP là đúng?

1. ACác bài toán không phải đa thức
2. BCác bài toán quyết định có câu trả lời "có" kiểm chứng được trong thời gian đa thức khi cho một chứng chỉ
3. CCác bài toán mà không thuật toán nào giải được
4. DCác bài toán không thể giải trong thời gian đa thức

Phát biểu nào về P và NP là đúng?

1. ANP có nghĩa là "không đa thức"
2. BĐã được chứng minh rằng P ≠ NP
3. CCác bài toán NP không thể được kiểm chứng nhanh
4. DMọi bài toán trong P cũng thuộc NP