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

Độ phức tạp thời gian trong trường hợp tốt nhất của sắp xếp chèn, trên một mảng đã sắp xếp, là gì?

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

Thời gian chạy nào sau đây là đa thức?

1. AO(nⁿ)
2. BO(n!)
3. CO(n³)
4. DO(2ⁿ)

Một thuật toán có hai vòng lặp lồng nhau, mỗi vòng chạy n lần, thường có độ phức tạp nào?

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

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

Thời gian chạy của sắp xếp cơ số LSD trên n số nguyên có d chữ số trong cơ số k là bao nhiêu?

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

Tìm kiếm theo chiều rộng trên một đồ thị không trọng số tìm ra:

1. AĐường đi ngắn nhất tính theo số cạnh từ nút xuất phát
2. BCây khung nhỏ nhất
3. CThứ tự tô-pô trong mọi đồ thị
4. DĐường đi ngắn nhất trong đồ thị có chứa các cạnh với trọng số âm

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

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

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

1. AĐã được chứng minh rằng P ≠ NP
2. BNP có nghĩa là "không đa thức"
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