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

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

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 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
3. Cf 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
4. Df tăng chậm hơn g một cách nghiêm ngặt

Độ 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)

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. CMọi logarit trong khoa học máy tính đều có cơ số 10, nên cơ số được ngầm hiểu
4. DLogarit luôn được làm tròn thành số nguyên

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

Trong bài toán chọn hoạt động, quy tắc tham lam nào luôn cho số hoạt động không chồng lấn tối đa?

1. AChọn hoạt động ngắn nhất trước
2. BChọn hoạt động có ít chồng lấn nhất trước, rồi lặp lại với các hoạt động tương thích
3. CChọn hoạt động kết thúc sớm nhất, rồi lặp lại với các hoạt động tương thích
4. DChọn hoạt động bắt đầu sớm nhất

Thuật toán quy hoạch động Held–Karp giải chính xác bài toán người bán hàng rong. Thời gian chạy của nó cho n thành phố là bao nhiêu?

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

Thuật toán Strassen nhân ma trận bằng 7 thay vì 8 phép nhân đệ quy các khối nửa kích thước. Thời gian chạy của nó là bao nhiêu?

1. AΘ(n³)
2. BΘ(n²)
3. CΘ(n^{log₂ 7}), khoảng n^2,81
4. DΘ(n² log n)