Độ 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)
Quảng cáo
Trả lời:

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.
Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay
- Trọng tâm Hóa học 11 dùng cho cả 3 bộ sách Kết nối, Cánh diều, Chân trời sáng tạo VietJack - Sách 2025 ( 58.000₫ )
- Trọng tâm Sử, Địa, GD KTPL 11 cho cả 3 bộ Kết nối, Chân trời, Cánh diều VietJack - Sách 2025 ( 38.000₫ )
- Sách lớp 11 - Trọng tâm Toán, Lý, Hóa, Sử, Địa lớp 11 3 bộ sách KNTT, CTST, CD VietJack ( 52.000₫ )
- Sách lớp 10 - Combo Trọng tâm Toán, Văn, Anh và Lí, Hóa, Sinh cho cả 3 bộ KNTT, CD, CTST VietJack ( 75.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1
A. Khi có vòng lặp lồng nhau
Lời giải
Đá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
Câu 2
A. Chương trình có độ phức tạp tuyến tính
Lời giải
Đá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.
Câu 3
A. Tuyến tính
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Câu 4
A. O(n)O(n)O(n)
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Câu 5
A. Khi chương trình có vòng lặp lồng nhau
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Câu 6
A. Quy tắc cộng
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.