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 xấu nhất của sắp xếp chèn là gì?

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

Thời gian chạy của sắp xếp đếm cho n số nguyên trong khoảng từ 0 đến k là bao nhiêu?

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

Tốc độ tăng O(2ⁿ) được gọi là gì?

1. AĐa thức
2. BTuyến tính
3. CHàm mũ
4. DLogarit

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 log n)
2. BΩ(n²)
3. CΩ(log n)
4. DΩ(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(n²)
3. CO(n log n)
4. DO(log 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(d(n + k))
2. BO(n log n)
3. CO(dn log k)
4. DO(n²)

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

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

Chi phí thời gian và không gian của việc tính số Fibonacci thứ n bằng một vòng lặp chỉ giữ hai giá trị cuối là bao nhiêu?

1. AThời gian O(n) và không gian O(1)
2. BThời gian O(log n) và không gian O(n)
3. CThời gian O(n) và không gian O(n)
4. DThời gian O(2ⁿ) và không gian O(1)