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

Big O của 3n² + 5n + 2 là gì?

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

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A1 giây
2. B4 giây
3. C8 giây
4. D2 giây

Thuật toán sắp xếp nào liên tục hoán đổi các phần tử kề nhau đang sai thứ tự?

1. ASắp xếp trộn
2. BSắp xếp vun đống
3. CSắp xếp nổi bọt
4. DQuicksort

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. AQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng
2. BSắp xếp trộn đã là O(n)
3. CCác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng
4. DSắp xếp trộn không có cấu trúc đệ quy

Độ phức tạp thời gian của thuật toán quy hoạch động chuẩn cho dãy con chung dài nhất của các chuỗi có độ dài m và n là gì?

1. AO(mn)
2. BO(mn log n)
3. CO(2^m+n)
4. DO(m + n)

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 20
2. BKhoảng 500,000
3. CKhoảng 100
4. DKhoảng 1,000

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²)

Vì sao mọi tìm kiếm dựa trên so sánh trong một mảng đã sắp xếp cần Ω(log n) phép so sánh trong trường hợp xấu nhất?

1. AMỗi phép so sánh mất thời gian logarit
2. BTìm kiếm nhị phân là thuật toán khả dĩ duy nhất, và nó cần log₂ n phép so sánh
3. CMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n
4. DMọi phần tử phải được so sánh ít nhất một lần