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

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng n / 2
2. BKhoảng n
3. CKhoảng log₂ n
4. DKhoảng n²

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

1. AHàm mũ
2. BĐa thức
3. CTuyến tính
4. DLogarit

Thời gian chạy của một thuật toán là O(n). Tốc độ tăng này được gọi là gì?

1. ALogarit
2. BTuyến tính
3. CHằng số
4. DBậc hai

Độ 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(m + n)
2. BO(mn)
3. CO(mn log n)
4. DO(2^m+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 log n)
2. BO(n²)
3. CO(log n)
4. DO(n)

Độ phức tạp thời gian của Fibonacci đệ quy ngây thơ (fib(n) = fib(n−1) + fib(n−2)) là:

1. ALogarit
2. BHàm mũ
3. CTuyến tính
4. DHằng số

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³)
2. BΘ(n log n)
3. CΘ(n^{log₂ 3}), khoảng n^1,585
4. DΘ(n²)

Định nghĩa nào của lớp P là đúng?

1. ACác bài toán quyết định giải được bằng thuật toán tất định trong thời gian đa thức
2. BCác bài toán có lời giải kiểm tra được nhưng không bao giờ tìm được trong thời gian đa thức
3. CCác bài toán cần thời gian hàm mũ trên mọi máy tính
4. DCác bài toán có thể giải song song