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?
A. 2+n+1=n+32 + n + 1 = n + 32+n+1=n+3
Giải bởi Vietjack
Đá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.
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ì?
Để 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?
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?
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ì?
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ì?
