Trắc nghiệm Tin học 11 Bài 24: Đánh giá độ phức tạp thời gian thuật toán - Kết nối tri thức

Đáp án: D

Giải thích: Phép nhân hai số có nnn chữ số sử dụng thuật toán Karatsuba có độ phức tạp O(n1.585)O(n^{1.585})O(n1.585), cải thiện từ O(n2)O(n^2)O(n2) của thuật toán thông thường.

Đáp án: A

Giải thích: Với chương trình 1, mỗi lệnh đơn tốn 1 đơn vị thời gian và có nnn bước trong vòng lặp, tổng thời gian là T1(n)=n+3T_1(n) = n + 3T1​(n)=n+3.

Đáp án: CBa

Giải thích: Do hai vòng lặp chạy lồng nhau với nnn lần, tổng độ phức tạp thời gian là O(n2)O(n^2)O(n2).

Đáp án: A

Giải thích: O(n)O(n)O(n) biểu thị độ phức tạp tuyến tính, tức là thời gian chạy tăng tuyến tính với kích thước đầu vào nnn.

Đáp án: B

Giải thích: Quy tắc cộng được áp dụng khi tính độ phức tạp thời gian của hai chương trình nối tiếp nhau, lấy giá trị độ phức tạp lớn nhất

Đáp án: A

Giải thích: Do n2n^2n2 là hàm bậc cao nhất, độ phức tạp thời gian của chương trình này là O(n2)O(n^2)O(n2).

Đáp án: C

Giải thích: Thuật toán sắp xếp chọn có độ phức tạp thời gian là O(n2)O(n^2)O(n2) do mỗi phần tử cần phải so sánh với các phần tử còn lại

Đáp án: B

Giải thích: Độ phức tạp O(1)O(1)O(1) có nghĩa là thời gian chạy không phụ thuộc vào kích thước đầu vào nnn.

Đáp án: B

Giải thích: O(logn) biểu thị thuật toán có độ phức tạp logarit, thường thấy trong các thuật toán như tìm kiếm nhị phân.

Đáp án: B

Giải thích: Khi tính độ phức tạp thời gian của các phép toán lồng nhau, quy tắc nhân được áp dụng.

Câu 1:

a) Sai, O(1) biểu thị độ phức tạp hằng số, không phụ thuộc vào kích thước đầu vào nnn, trong khi độ phức tạp của chương trình 1 phụ thuộc tuyến tính vào nnn.

b) Sai. O(log n) chỉ đúng cho các thuật toán mà thời gian tính toán tăng tỷ lệ logarit với nnn, điều này không đúng trong chương trình 1.

c) Đúng. O(n) nghĩa là thời gian tính toán tăng tuyến tính với kích thước đầu vào nnn, phù hợp với hàm T1(n)=n+3T_1(n) = n + 3T1​(n)=n+3.

d) Sai. O(n²) mô tả độ phức tạp bậc hai, thường xuất hiện ở các thuật toán có vòng lặp lồng nhau, điều này không áp dụng cho chương trình 1.

a) Sai. O(n) biểu thị độ phức tạp tuyến tính, không phù hợp với T2(n)=n2+3T_2(n) = n^2 + 3T2​(n)=n2+3, vì thời gian tính toán của chương trình 2 tăng theo bậc hai của nnn.

b) Đúng. O(n²) biểu thị độ phức tạp bậc hai, phù hợp với cấu trúc vòng lặp lồng nhau của chương trình 2.

c) Sai. O(log n) biểu thị độ phức tạp logarit, thường gặp ở các thuật toán chia để trị, không áp dụng cho chương trình 2.

d) Sai. O(1) nghĩa là độ phức tạp hằng số, không thay đổi với kích thước đầu vào, không đúng với chương trình 2.

Đáp án: Độ phức tạp thời gian của chương trình 1 là O(n)

Giải thích: Chương trình 1 thực hiện một lệnh gán và một vòng lặp với n bước, trong đó mỗi bước của vòng lặp thực hiện một phép toán. Tổng thời gian chạy được tính là T₁(n) = 2 + n + 1 = n + 3, do đó khi n lớn, thời gian chạy có thể ước lượng là O(n), tức là tuyến tính.

Đáp án: Độ phức tạp thời gian của chương trình 2 là O(n²).

Giải thích: Chương trình 2 có hai vòng lặp lồng nhau, mỗi vòng lặp đều chạy n lần. Vì vậy, tổng số phép toán sẽ là n * n = n². Thời gian chạy được tính là T₂(n) = 2 + 2 + 1 + n² + n² + 3 = n² + 5, do đó khi n lớn, thời gian chạy có thể ước lượng là O(n²), tức là bình phương.

Đáp án: Việc ước lượng thời gian chạy giúp lập trình viên hiểu rõ hơn về hiệu suất của thuật toán và tối ưu hóa mã nguồn.

Giải thích: Khi phát triển phần mềm, thời gian thực hiện của các thuật toán có thể ảnh hưởng lớn đến hiệu suất tổng thể của ứng dụng. Hiểu độ phức tạp thời gian giúp lập trình viên lựa chọn thuật toán phù hợp nhất cho dữ liệu đầu vào lớn, từ đó cải thiện khả năng xử lý và tiết kiệm tài nguyên máy tính.