15 câu Trắc nghiệm Tin học 11 KNTT Định hướng Khoa học máy tính Bài 24: Đánh giá độ phức tạp thời gian thuật toán có đáp á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?

Trong chương trình 1 ở Hình 24.2, tổng số đơn vị thời gian để thực hiện toàn bộ chương trình là bao nhiêu?

Trong chương trình 2 ở Hình 24.2, độ phức tạp thời gian của vòng lặp lồng nhau là gì?

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ì?

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?

Nếu chương trình có độ phức tạp thời gian T(n)=n2+3n+1T(n) = n^2 + 3n + 1T(n)=n2+3n+1, độ phức tạp thời gian của nó là gì?

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

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)?

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ì?

Để 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 1 trong Hình 24.2, với tổng thời gian tính toán là T1(n)=n+3T_1(n) = n + 3T1​(n)=n+3, được đánh giá là:

a) O(1)

b) O(log n)

c) O(n)

d) O(n²)

Độ 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)

Độ phức tạp thời gian của chương trình 1 trong hình 24.2 là gì?

Độ phức tạp thời gian của chương trình 2 trong hình 24.2 là gì?

Tại sao việc ước lượng thời gian chạy của chương trình lại quan trọng trong lập trình?