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

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. BHằng số
3. CBậc hai
4. DTuyến tính

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig O
2. BBig Theta
3. CBig Omega
4. DLittle omega

Độ 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 + E)
2. BO(V × E)
3. CO(E log V)
4. DO(V²)

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

1. AHằng số
2. BHàm mũ
3. CTuyến tính
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Ω(log n)
2. BΩ(n log n)
3. CΩ(n)
4. DΩ(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 bắt đầu sớm nhất
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 ngắn nhất trước
4. DChọ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

Công thức truy hồi T(n) = 2T(n/2) + n log n có nghiệm là gì?

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

Định lý Cook–Levin đã thiết lập điều gì?

1. AMọi bài toán NP đều giải được trong thời gian hàm mũ
2. BBài toán thỏa mãn Boole (SAT) là NP-đầy đủ
3. CP không bằng NP
4. DBài toán dừng là bất khả quyết định