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ì?
A. O(n)O(n)O(n)
Giải bởi Vietjack
Đáp án: C
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).
Để 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?
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?
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?
Ký hiệu O(logn)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Ầ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?
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ì?
