PHẦN I. Câu trắc nghiệm nhiều phương án lựa chọn. Thí sinh trả lời từ câu 1 đến câu 10. Mỗi câu hỏi thí sinh chỉ lựa chọn một phương án.

Độ phức tạp thời gian của phép nhân hai số nguyên có nnn chữ số, như trong ví dụ của Karatsuba, là bao nhiêu?

Quy tắc cộng trong tính độ phức tạp thời gian của thuật toán được áp dụng trong trường hợp nào?

Ký hiệu O(n)O(n)O(n) trong phân tích độ phức tạp thời gian biểu thị điều gì?

Ký hiệu O(log⁡n)O(\log n)O(logn) được dùng khi độ phức tạp thời gian của thuật toán là gì?

Trong trường hợp nào độ phức tạp thời gian của chương trình là O(1)O(1)O(1)?

Độ phức tạp thời gian của thuật toán sắp xếp chọn là bao nhiêu?

Để tính độ phức tạp thời gian của chương trình với các phép toán lồng nhau, ta áp dụng quy tắc nào?

Độ phức tạp thời gian của chương trình 2 trong Hình 24.2, với tổng thời gian tính toán là T2(n)=n2+3T_2(n) = n^2 + 3T2​(n)=n2+3, được đánh giá là:

a) O(n)

b) O(n²)

c) O(log n)

d) O(1)