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

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

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

Độ phức tạp thời gian của tìm kiếm theo chiều sâu trên một đồ thị lưu bằng danh sách kề là gì?

1. AO(V²)
2. BO(V × E)
3. CO(V + E)
4. DO(E log V)

Phát biểu nào về một hàm đệ quy không có trường hợp cơ sở nào đạt tới được là đúng?

1. ANó cứ gọi chính nó cho đến khi ngăn xếp lời gọi bị tràn
2. BTrình biên dịch luôn biến nó thành một vòng lặp kết thúc an toàn
3. CNó tự động trả về 0
4. DNó chạy trong thời gian O(1)

Độ phức tạp thời gian của: for i = 1 to n: for j = 1 to i: thực hiện công việc O(1) là gì?

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

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

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

n! và 2ⁿ so sánh với nhau thế nào khi n lớn?

1. A2ⁿ tăng nhanh hơn n!
2. Bn! tăng nhanh hơn 2ⁿ
3. CChúng tăng với cùng tốc độ
4. Dn! là O(n²)

Dùng định lý chủ, T(n) = 8T(n/2) + O(n²) có nghiệm là:

1. AΘ(n²)
2. BΘ(n³)
3. CΘ(n log n)
4. DΘ(n² log n)