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

Một thuật toán O(n) mất 3 giây khi n = 1 triệu. Khoảng bao lâu khi n = 2 triệu?

1. A6 giây
2. B12 giây
3. C9 giây
4. D3 giây

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

Độ phức tạp không gian đo lường:

1. AKích thước vật lý của máy tính
2. BLượng bộ nhớ một thuật toán cần khi đầu vào tăng
3. CDung lượng đĩa của tệp chương trình sau khi được biên dịch
4. DSố dòng mã

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

1. AO(n log n)
2. BO(n²)
3. CO(log n)
4. DO(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 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
2. BChọ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
3. CChọn hoạt động ngắn nhất trước
4. DChọn hoạt động bắt đầu sớm nhất

Độ phức tạp thời gian của việc nhân hai ma trận n × n bằng ba vòng lặp lồng nhau chuẩn là gì?

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

Thuật toán Strassen nhân ma trận bằng 7 thay vì 8 phép nhân đệ quy các khối nửa kích thước. Thời gian chạy của nó là bao nhiêu?

1. AΘ(n³)
2. BΘ(n^{log₂ 7}), khoảng n^2,81
3. CΘ(n²)
4. DΘ(n² log n)

Phát biểu nào về ký hiệu little-o là đúng?

1. An = o(n²), nhưng n không phải o(n)
2. Bn = o(n), vì mọi hàm đều là little-o của chính nó
3. C2n = o(n), vì 2n tăng chậm
4. Dn² = o(n)