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)?
A. Khi chương trình có vòng lặp lồng nhau
Giải bởi Vietjack
Đá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.
Để 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ì?
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ì?
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Ầ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ì?
